[LeetCode] 145.二叉樹的後序周遊（java實作、非遞歸法）

• 1. 題目
• 2. 讀題（需要重點注意的東西）
• 3. 解法
• 4. 可能有幫助的前置習題
• 5. 所用到的資料結構與算法思想
• 6. 總結

1. 題目

2. 讀題（需要重點注意的東西）

使用二叉樹的後序周遊模闆，可以使用遞歸很簡單的解決這個問題。但是你能否使用非遞歸的方法實作二叉樹的後序周遊呢？

（先序周遊和後序周遊的關系：先序周遊為中左右、後序周遊為左右中，使用棧時，入棧順序為左右時，出棧順序為中右左（因為中結點出棧後、左右孩子才入棧），是以對出棧後的資料進行倒置，就為左右中，即後序周遊）

3. 解法

解法：非遞歸法

需要注意的是，二叉樹的前序周遊是中左右，是以在入棧時，需要先入右孩子，再入左孩子，這樣輸出出來的結果才是中左右。又因為二叉樹的後序周遊是按左右中進行周遊。是以在實際入棧時，先入左孩子，再入右孩子，由于棧的先入後出的特性，出棧的結果為中右左，再對輸出的結果進行翻轉，就能得到左右中的周遊順序，即後序周遊。

/**
 * 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> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return list;
        // 将第一個根節點壓入棧
        stack.push(root);
        // 用棧實作疊代
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        Collections.reverse(list);
        return list;
    }
}
           

4. 可能有幫助的前置習題

• 二叉樹的先序周遊

5. 所用到的資料結構與算法思想

• 棧

6. 總結

要使用非遞歸的方式解決這道題，就需要了解前序周遊、後序周遊的思想以及先序周遊與後序周遊的關系和它們的實作過程，再結合這個過程使用合适的資料結構（如若需要先進先出，使用隊列；若需要先進後出，使用棧，等等）進行操作。