145. 二叉樹的後序周遊

1.題目描述

給定一個二叉樹，傳回它的後序周遊。

示例:

進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？

2.方法1

先序周遊是中左右，後續周遊是左右中，那麼我們隻需要調整一下先序周遊的代碼順序，就變成中右左的周遊順序，然後在反轉result數組，輸出的結果順序就是左右中了，如下圖：

3.代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL){
            return res;
        }
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* node = s.top();
            s.pop();
            res.push_back(node->val);
            if(node->left){
                s.push(node->left);
            }
            if(node->right){
                s.push(node->right);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
           

4.複雜度分析

時間複雜度：O(n)

空間複雜度：O(n)

5.方法2

按照左右中的順序周遊，一直把root的左節點入棧直到為空

1.此時棧頂元素為樹的最左節點，出棧

2.如果最左節點有右子樹，則把右子節點入棧，往右子樹周遊

3.如果最左節點沒有右子樹，則把目前節點加入結果數組，并記錄目前節點為pre，當節點出棧時，如果節點的右子節點等于pre，則把節點加入結果數組。并把目前節點置空，防止重複周遊。

6.代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL){
            return res;
        }
        stack<TreeNode*> s;
        TreeNode* pre = NULL;
        while(root != NULL || !s.empty()){
            while(root != NULL){
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            if(root->right == NULL || root->right == pre){
                res.push_back(root->val);
                pre = root;
                root = NULL;
            }
            else{
                s.push(root);
                root = root->right;
            }
        }
        return res;
    }
};
           

7.複雜度分析

時間複雜度：O(n)

空間複雜度：O(n)