LeetCode 145.二叉树的后序遍历

Posted on | In

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例 

1
2
3
4
5
6
7
8
9
> 输入: [1,null,2,3]  
>    1
>     \
>      2
>     /
>    3 
> 
> 输出: [3,2,1]
>

思路:

  1. 前序遍历的方式是 root->left->right的顺序.

  2. 后序遍历的方式是left->right->root,

  3. 我们可以把前序改为后序先root->right->left然后reverse下就可以得到后序遍历了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root)  return {};
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || !st.empty()){
            while (cur){
                ans.push_back(cur->val);       // 先root
                st.push(cur);
                cur = cur->right; 			   // 再 right
            }
            cur = st.top();
            st.pop();
            cur = cur->left;					//最后 left
        }
        // reverse 之后 left->right->root刚好为后序遍历的方式
        reverse(ans.begin(), ans.end());     
        return ans;
    }
};