首页 > 代码库 > Leetcode: Binary Tree Preorder Traversal
Leetcode: Binary Tree Preorder Traversal
这道题一共有三道解法：
其中第二种解法，我参考了迭代器的写法，写了一个迭代器的类。重载了前++和—>操作符，但是这个解法会造成内存的超限，很奇怪，
解法1：递归解法：
1 class Solution { 2 public: 3 vector<int> result; 4 vector<int> preorderTraversal(TreeNode *root) { 5 6 rpreorde(root); 7 return result; 8 } 9 void rpreorde(TreeNode *root)10 {11 if(root == NULL)12 return ;13 result.push_back(root->val);14 rpreorde(root->left);15 rpreorde(root->right);16 17 18 }19 };
第二种解法迭代器
1 class Solution { 2 public: 3 4 typedef TreeNode * STreeNode; 5 vector<int> preorderTraversal(TreeNode *root) { 6 7 stack<STreeNode> buf; 8 nodeiterator temp(root,buf); 9 vector<int> result;10 11 for(;temp.NotDone();++temp)12 {13 result.push_back(temp->val);14 15 }16 17 18 return result;19 }20 class nodeiterator21 {22 public:23 24 stack<STreeNode>& buf;25 STreeNode pcurrent;26 nodeiterator(TreeNode *root,stack<STreeNode>& data):pcurrent(root),buf(data){}27 void operator++()28 {29 if(pcurrent->left != NULL)30 {31 buf.push(pcurrent);32 pcurrent = pcurrent->left;33 return ;34 35 }36 if(pcurrent->right != NULL)37 {38 pcurrent = pcurrent->right;39 return ;40 }41 pcurrent = NULL;42 while(buf.size()!=0)43 {44 pcurrent = buf.top();45 buf.pop();46 if(pcurrent->right != NULL)47 {48 pcurrent = pcurrent->right;49 break;50 }51 52 pcurrent = NULL;53 }54 55 }56 57 TreeNode* operator->()58 {59 return pcurrent;60 61 }62 TreeNode& operator*()63 {64 return *pcurrent;65 66 }67 bool NotDone()68 {69 if(pcurrent == NULL)70 return false;71 else72 return true;73 }74 75 };76 };
第三种解法：
class Solution {public: typedef TreeNode * STreeNode; vector<int> preorderTraversal(TreeNode *root) { stack<STreeNode> buf; vector<int> result; STreeNode pcurrent; pcurrent = root; while(pcurrent != NULL) { result.push_back(pcurrent->val); if(pcurrent->left != NULL) { buf.push(pcurrent); pcurrent = pcurrent->left; continue; } if(pcurrent->right != NULL) { pcurrent = pcurrent->right; continue ; } pcurrent = NULL; while(buf.size()!=0) { pcurrent = buf.top(); buf.pop(); if(pcurrent->right != NULL) { pcurrent = pcurrent->right; break; } pcurrent = NULL; } } return result; } };
Leetcode: Binary Tree Preorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。