首页 > 代码库 > leetcode[145] Binary Tree Postorder Traversal
leetcode[145] Binary Tree Postorder Traversal
实现后序遍历
递归：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void helper(TreeNode *root, vector<int> &perm) { if (!root) return; helper(root -> left, perm); helper(root -> right, perm); perm.push_back(root -> val); } vector<int> postorderTraversal(TreeNode *root) { vector<int> ans; helper(root, ans); return ans; }};
非递归：
非递归使用栈。首先把根节点压栈，然后循环如下操作：用一个变量来记录上次访问的节点，如果当前栈顶元素左右儿子都为空 或者 上次访问的节点非空且等于栈顶节点的左儿子或右儿子，则直接访问；否则把栈顶元素的右节点和左节点依次压栈。
/** * 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> perm; if (!root) return perm; stack<TreeNode *> sta; TreeNode *p = root, *pre = NULL; sta.push(p); while(!sta.empty()) { p = sta.top(); if (!p->left && !p->right) { perm.push_back(p->val); pre = p; sta.pop(); } if (pre && (pre == p -> left || pre == p -> right)) { perm.push_back(p -> val); pre = p; sta.pop(); } else { if (p -> right) sta.push(p -> right); if (p -> left) sta.push(p -> left); } } return perm; }};
再来一个比较有意思的解法，就是利用前序遍历实现后序遍历，只要在考虑前序遍历的根左右的过程改为根右左，然后将结果反转reverse一下就可以了。
/** * 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> perm; stack<TreeNode *> sta; TreeNode *p = root; while(!sta.empty() || p) { while(p) { perm.push_back(p->val); if (p -> left) sta.push(p -> left); p = p -> right; } if (!sta.empty()) { p = sta.top(); sta.pop(); } } reverse(perm.begin(), perm.end()); return perm; }};
leetcode[145] Binary Tree Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。