LeetCode 145. 二叉樹的后序遍歷【c++/java詳細題解】

1、題目

給定一個二叉樹，回傳它的 后序 遍歷，

示例:

輸入: [1,null,2,3]  
   1
    \
     2
    /
   3 

輸出: [3,2,1]

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

2、思路1

(遞回） O ( n ) O(n) O(n)

給定一個二叉樹，回傳它的 后序 遍歷，

樣例：

如樣例所示，該二叉樹的后序遍歷為res = [9,5,7,4,3]，下面來講解遞回的做法，

二叉樹的后序遍歷順序為：左->右->根，因此我們直接按照 左子樹—>右子樹—>根節點的方式遍歷這顆二叉樹，

遞回函式設計：

void dfs(TreeNode* root)

root是當前訪問的節點，

遞回邊界：

當訪問到空節點時，結束本次遞回呼叫，

具體程序如下：

• 1、定義res陣列用來存貯訪問后的節點，
• 2、從根節點root開始遞回，
• 3、遞回呼叫dfs(root->left)和dfs(root->right)來遍歷當前root節點的左右子樹，
• 4、將當前root節點的val值加入res陣列中，

時間復雜度分析： O ( n ) O(n) O(n) ，其中 n n n是二叉樹的節點數，每一個節點恰好被遍歷一次，

3、c++代碼

/**
 * 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>res;
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root)
    {
        if(root == NULL) return;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }
};

4、java代碼

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }
     public void dfs(TreeNode root)
    {
        if(root == null) return;
        dfs(root.left);
        dfs(root.right);
        res.add(root.val);
    }
}

5、思路2

(迭代) O ( n ) O(n) O(n)

迭代演算法的本質是模擬遞回，只不過遞回使用了系統堆疊，而在迭代演算法中我們使用stack模擬系統堆疊，在 144. 二叉樹的前序遍歷 題中，我們已經知道了前序遍歷二叉樹的迭代寫法，因此如何更改少量的代碼實作二叉樹的后序遍歷？

二叉樹的前序遍歷順序為：根->左->右，后序遍歷的順序為：左->右->根，我們將后序遍歷的順序顛倒過來為：根->右->左，因此我們只需要模擬前序遍歷的程序，并將前序遍歷中的左右子樹遍歷程序對換，最后將遍歷得到的res陣列翻轉即可得到后序遍歷的結果，

具體程序如下：

對于二叉樹中的當前節點root：

• 1、將當前節點壓入堆疊中，并記錄到res陣列中，
• 2、如果當前節點還有右兒子的話，繼續將其右兒子壓入堆疊中，
• 3、重復上述程序，直到最后一個節點沒有右兒子為止，

這樣，我們就將當前節點root和它的右側子節點全部訪問完畢了（相當于我們已經訪問了根節點和右子樹節點），堆疊中存放著當前節點和它的全部右側子節點，接下來我們該要去訪問當前節點的左子樹了，由于堆疊是先進后出的，此時堆疊頂元素的左子節點就是下一個要遍歷的節點，因此

• 1、取出堆疊頂元素的左子節點，并將其彈出堆疊，
• 2、如果當前堆疊頂元素的左子節點不為空，我們繼續將其當成當前節點root，重復對當前節點root的處理程序，
• 3、最后將得到的res陣列翻轉，

時間復雜度分析： O ( n ) O(n) O(n) ，其中 n n n是二叉樹的節點數，每一個節點恰好被遍歷一次，

6、c++代碼

/**
 * 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) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root || stk.size()) {
            while (root) {
                res.push_back(root->val);
                stk.push(root);
                root = root->right;
            }
            root = stk.top()->left;
            stk.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

7、java代碼

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<Integer>();
       Stack<TreeNode> stk = new Stack<TreeNode>();
       while(root != null || !stk.isEmpty())
       {
           while(root != null)
           {
               res.add(root.val);
               stk.add(root);
               root = root.right;
           }
           root = stk.pop();
           root = root.left;
       }
       Collections.reverse(res);
       return res;
   }
}

原題鏈接： 145. 二叉樹的后序遍歷