首页 > 代码库 > 【leetcode】Binary Tree Postorder Traversal
【leetcode】Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
1st （ 2 tries）
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; *///help from http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html//there is all kind all traversal methods with binary tree in this class Solution {public: vector<int> postorderTraversal(TreeNode *root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. TreeNode *iter = NULL; TreeNode *preiter = NULL; vector<int> re; stack<TreeNode*> st; if(root == NULL) return re; st.push(root); while(!st.empty()) { iter = st.top(); if(iter->left == NULL&&iter->right == NULL) { re.push_back(iter->val); preiter = iter; st.pop(); } else if(preiter != NULL && (preiter == iter->left || preiter == iter->right)) { re.push_back(iter->val); preiter = iter; st.pop(); } else { if(iter->right != NULL) st.push(iter->right); if(iter->left != NULL) st.push(iter->left); } } return re; }};
2nd （15 tries)
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: //learn morris post-order traversal!!! this is most difficult!!! vector<int> ans; vector<int> postorderTraversal(TreeNode *root) { //now I can‘t get the iterative postorder traversal //rethink!!! //now I just remember preorder traversal //preorder and inorder are not so differcut,just change ans.push_back() position!!! //postorder??? /* stack<TreeNode*> s; vector<TreeNode*> roots; TreeNode *cur = root; while(!s.empty() || cur != NULL) { while(cur != NULL) { s.push(cur); cur = cur->left; } cur = s.top(); //now the root have out of stack,how to save it??? //This method change Tree structure???how to don‘t change tree structure!!! //using flag is one method!!! if(cur->right == NULL) { ans.push_back(cur->val); s.pop(); cur = cur->right; } else { TreeNode *pre = cur; cur = cur->right; pre->right = NULL; } } return ans; */ //use one stack to obtain postorderTraversal //root , right, left then reverse the vector!!! //!!! /* stack<TreeNode*> s; stack<TreeNode*> post; TreeNode *cur = root; while( !s.empty() || cur != NULL ) { while(cur != NULL ) { ans.push_back(cur->val); s.push(cur); cur = cur->right; } cur = s.top(); s.pop(); cur = cur->left; } vector<int> res; while( !post.empty() ) { ans.push_back(post.top()->val); post.pop(); } reverse(ans.begin(),ans.end()); return ans; */ //another method is using prev!!! //link:http://leetcode.com/2010/10/binary-tree-post-order-traversal.html if(root == NULL) return ans; stack<TreeNode*> s; s.push(root); TreeNode *cur = NULL,*pre = NULL; while( !s.empty() ) { cur = s.top(); if( pre == NULL || pre->left == cur || pre->right == cur ) { if(cur->left != NULL) s.push(cur->left); else if(cur->right != NULL) s.push(cur->right); } else if( cur->left == pre ) { if( cur->right != NULL ) s.push(cur->right); } else { ans.push_back(cur->val); s.pop(); } pre = cur; } return ans; } /* void dfs(TreeNode *root) { if(root == NULL) return; dfs(root->left); dfs(root->right); ans.push_back(root->val); } */};
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> ans; void reverse(TreeNode *from,TreeNode *to) { TreeNode *cur = from->left; TreeNode *post = cur->right; //reverse covery like reverse link list... while( cur != to ) { TreeNode *post_right = post->right; post->right = cur; cur = post; post = post_right; } while( cur != from->left ) { ans.push_back(cur->val); cur = cur->right; } ans.push_back(cur->val); } void reversecover(TreeNode *from,TreeNode *to) { TreeNode *cur = from; TreeNode *post = cur->right; TreeNode *end = to->left; //just reverse like reverse link list while( cur != end ) { TreeNode *post_right = post->right; post->right = cur; cur = post; post = post_right; } from->right = to; } vector<int> postorderTraversal(TreeNode *root) { //morris TreeNode *newroot = new TreeNode(0); newroot->left = root; newroot->right = NULL; TreeNode *cur = newroot,*pre = NULL; while( cur != NULL ) { if( cur->left == NULL ) { cur = cur->right; } else { pre = cur->left; while( pre->right != NULL && pre->right != cur ) { pre = pre->right; } if( pre->right == NULL ) { pre->right = cur; cur = cur->left; } else { //post-order here //reverse reverse(cur,pre); //reverse-cover reversecover(pre,cur); //over pre->right = NULL; cur = cur->right; } } } return ans; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。