***Leetcode 145. Binary Tree Postorder Traversal

本文主要是介绍***Leetcode 145. Binary Tree Postorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

给一种容易理解的写法：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> sta;unordered_set< TreeNode*> visit;vector<int> ans;TreeNode* cur = root;if (root) sta.push(root);while (sta.size()) {root = sta.top();int cnt = 0;if (root->right && !visit.count(root->right)) {sta.push(root->right);cnt ++;} if (root->left && !visit.count(root->left)) {sta.push(root->left);cnt ++;}if (cnt == 0) {ans.push_back(root->val);visit.insert(root);sta.pop();} }return ans;}
};

这里看到的更好的写法，不需要存visit https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45550/0-ms-Clear-C++-solutions-iterative-recursive-Morris-traversal-(3-different-solutions!)

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> sta;// set< TreeNode*> visit;vector<int> ans;TreeNode* cur = root, *last = NULL;while (cur || sta.size()) {if (cur) {sta.push(cur);cur = cur -> left;} else {TreeNode* tp = sta.top();if ( tp->right && last != tp->right) {cur = tp->right;} else {ans.push_back( tp->val );last = tp;sta.pop();}}}return ans;}
};

这篇关于***Leetcode 145. Binary Tree Postorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---