LeetCode_Stack_145. Binary Tree Postorder Traversal 二叉樹的後序周遊（Java）【棧，疊代】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一博​​

一，題目描述

英文描述

Given the root of a binary tree, return the postorder traversal of its nodes' values.

中文描述

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

示例與說明

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Constraints:

The number of the nodes in the tree is in the range [0, 100].

-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/binary-tree-postorder-traversal​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

參考官方題解​​@力扣官方題解【 二叉樹的後序周遊】​​

關鍵在于用棧模拟遞歸的過程，包括遞歸的進度、遞歸的狀态。

• 遞歸的進度：标明周遊到了哪個節點；
• 遞歸的狀态：标明左右子樹是否已周遊；

隻要能記錄上面兩種資訊，不管什麼方法都可以。

官方題解中采用棧stack來記錄遞歸的進度，prev節點記錄遞歸的狀态。

• stack：遵循先左後右的規則将節點入棧，每輸出一個值到結果數組中時，将該節點從棧裡徹底彈出（不再入棧）；
• prev：記錄周遊的上一節點，用來判斷右子樹是否已經周遊（以下圖為例，周遊完節點7後，将其标記為prev。當周遊到下一個節點4時，憑借root.right == prev?來判斷右子樹是否已周遊）；

三，AC代碼

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> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            // 一路向左 左節點入棧
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // 到這裡時 已經可以表示左子樹為空或者左子樹已經全部周遊過
            // 葉子節點、右節點為空或者右子樹已周遊 将節點值存入結果數組
            // pre = root 将來用于判斷右子樹是否已周遊
            if (root.right == null || root.right == pre) {
                ans.add(root.val);
                pre = root;
                root = null;
            } else {
                // 根節點重新入棧（因為根節點的值還沒有輸出到結果數組中）
                // 并将右子樹節點調整為新根節點 開始新子樹的疊代
                stack.push(root);
                root = root.right;
            }
        }
        return ans;
    }
}      

Java中的棧通常用雙端隊列deque實作，具體用法可以看這裡​​@devnn【【Java】Java雙端隊列Deque使用詳解】​​

四，解題過程

第一博