首页 > 代码库 > 【LeetCode】Binary Tree Postorder Traversal (3 solutions)
【LeetCode】Binary Tree Postorder Traversal (3 solutions)
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?
解法一：递归法
/** * 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> postorderTraversal(TreeNode *root) { vector<int> ret; postOrder(root, ret); return ret; } void postOrder(TreeNode* root, vector<int>& ret) { if(root == NULL) return; postOrder(root->left, ret); postOrder(root->right, ret); ret.push_back(root->val); }};
解法二：借助栈的非递归回溯解法。由于不能在树节点中增加visited成员，所以开辟map进行访问记录。
需要注意的是，出栈（即结束访问）有两种情况：
（1）左右节点均为空，即叶节点
（2）左右节点均已访问过
/** * 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> postorderTraversal(TreeNode *root) { vector<int> ret; if(root == NULL) return ret; map<TreeNode*, bool> m; //visited stack<TreeNode*> s; s.push(root); m.insert(map<TreeNode*, bool>::value_type(root, true)); while(!s.empty()) { TreeNode* cur = s.top(); while(cur->left) { TreeNode* left = cur->left; map<TreeNode*, bool>::iterator it = m.find(left); if(it == m.end()) {//not visited s.push(left); m.insert(map<TreeNode*, bool>::value_type(left, true)); cur = left; //down left } else break; //cur remains } if(cur->right) { TreeNode* right = cur->right; map<TreeNode*, bool>::iterator it = m.find(right); if(it == m.end()) {//not visited s.push(right); m.insert(map<TreeNode*, bool>::value_type(right, true)); cur = right; //down right } else {//cur finish ret.push_back(cur->val); s.pop(); } } else {//cur finish ret.push_back(cur->val); s.pop(); } } return ret; }};
解法三：在Discussion看到一种神一样的解法。
前序是：根左右
后续是：左右跟
因此可以将前序改为根右左，然后逆序为左右根输出。
前序遍历不需要回溯（对应图的深度遍历），是一种半层次遍历，因此效率很高。
/** * 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> postorderTraversal(TreeNode *root) { vector<int> ret; if(root == NULL) return ret; stack<TreeNode*> s; s.push(root); while(!s.empty()) { TreeNode* cur = s.top(); s.pop(); ret.push_back(cur->val); if(cur->left) s.push(cur->left); if(cur->right) s.push(cur->right); } reverse(ret.begin(), ret.end()); return ret; }};
【LeetCode】Binary Tree Postorder Traversal (3 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。