来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个二叉树,返回它的 后序 遍历。
例如输入[1,null,2,3] :
1 2 3 4 5 |
1 \ 2 / 3 |
输出:
1 |
[3,2,1] |
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
二、题解
参考:二叉树的后序遍历。
三、代码
3.1 通过栈+链表实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/** * Definition for a binary tree node. * 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) { stack<TreeNode *> s; list<TreeNode *> l; vector<int> v; TreeNode *p; if (root == nullptr) { return v; } s.push(root); while (!s.empty()) { p = s.top(); s.pop(); l.push_front(p); if (p->left) { s.push(p->left); } if (p->right) { s.push(p->right); } } while(!l.empty()) { v.push_back(l.front()->val); l.pop_front(); } return v; } }; |
3.2 通过2次压栈实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { TreeNode *p; vector<int> v; stack<TreeNode *> st; if (root == nullptr) { return v; } st.push(root); st.push(root); while (!st.empty()) { p = st.top(); st.pop(); if (!st.empty() && st.top() == p) { if (p->right) { st.push(p->right); st.push(p->right); } if (p->left) { st.push(p->left); st.push(p->left); } } else { v.push_back(p->val); } } return v; } }; |
评论