二叉樹的三種周遊實作(疊代法)

二叉樹的三種周遊（不同疊代法實作）

前序周遊

二叉樹的前序周遊

前序周遊的順序是中左右，我們可以建立一個棧，利用棧的特性幫助我們前序周遊二叉樹，先将二叉樹的根節點入棧，再将根節點出棧，加入到結果集中，再将根節點的右子節點先入棧，左子節點再入棧，注意：空節點不入棧，再判斷棧頂是否為空，為空則出棧，将出棧的節點加入到結果集中。為什麼右子節點比左子節點先入棧，因為這樣右子節點就比左子節點後出棧，節點出棧的順序就是中左右了，正好和二叉樹的前序周遊順序一樣。

Java代碼如下：

class Solution {
    /**
     * 疊代法實作二叉樹的前序周遊
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        // 聲明一個動态數組存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            // 注意右子節點比左子節點先入棧，這樣出棧順序就是中左右了
            // 将右子節點入棧
            if (node.right != null) {
                stack.push(node.right);
            }
            // 将左子節點入棧
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }
}
           

中序周遊

二叉樹的中序周遊

因為二叉樹先通路的節點是中節點，而程式先處理的節點也是中節點，是以二叉樹的前序周遊用疊代法實作比較簡潔。

而中序周遊的疊代法就和前序周遊的疊代法有些不同，需要還借助一個指針幫助實作。

class Solution {
    /**
     * 疊代法實作二叉樹的中序周遊，需要借助一個指針
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 聲明一個動态數組，用來存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root; // 先從根節點開始
        while (cur != null || !stack.isEmpty()) {
            // 如果cur == null，說明已找到最左子節點
            if (cur != null) {
                stack.push(cur);
                cur = cur.left; // 左
            } else {
                cur = stack.pop();
                res.add(cur.val); // 中
                cur = cur.right; // 右
            }
        }
        return res;
    }
}
           

後序周遊

二叉樹的後序周遊

後序周遊的順序是左右中，我們隻需稍稍改變前序周遊的疊代法實作，得到周遊順序為中右左的結果集，再将結果集翻轉就可以得到後序周遊為左右中的結果集了。

class Solution {
    /**
     * 疊代法實作二叉樹的後序周遊
     * 隻需用疊代法得到中右左的結果集順序，最後将結果集翻轉即可
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        // 聲明一個動态數組，用來存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); // 先将根節點的值加入到棧中
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            // 将左子節點入棧
            if (node.left != null) {
                stack.push(node.left);
            }
            // 将右子節點入棧
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        // 調用Collections類的reverse方法翻轉res
        Collections.reverse(res);
        return res;
    }
}
           

二叉樹的三種周遊（統一疊代法實作）

當要處理的節點放入棧中，可以再放入一個空節點做标記來實作

前序周遊

class Solution {
    /**
     * 統一疊代法得到二叉樹的前序周遊結果
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        // 聲明一個動态數組，用來存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); // 先将根節點的值加入到棧中
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                if (node.right != null) {
                    stack.push(node.right); // 右
                }
                if (node.left != null) {
                    stack.push(node.left); // 左
                }
                stack.push(node); // 中
                stack.push(null); // 空指針做标記
            } else {
                stack.pop();
                node = stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}
           

中序周遊

class Solution {
    /**
     * 統一疊代法得到二叉樹的中序周遊結果
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 聲明一個動态數組，用來存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); // 先将根節點的值加入到棧中
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                if (node.right != null) {
                    stack.push(node.right); // 右
                }
                stack.push(node); // 中
                stack.push(null); // 空指針做标記
                if (node.left != null) {
                    stack.push(node.left); // 左
                }
                
            } else {
                stack.pop();
                node = stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}
           

後序周遊

class Solution {
    /**
     * 統一疊代法得到二叉樹的後序周遊結果
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 聲明一個動态數組，用來存放結果
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); // 先将根節點的值加入到棧中
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                stack.push(node); // 中
                stack.push(null); // 空指針做标記
                if (node.right != null) {
                    stack.push(node.right); // 右
                }
                if (node.left != null) {
                    stack.push(node.left); // 左
                }
                
            } else {
                stack.pop();
                node = stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}