經(jīng)典Java面試題解析：二叉樹的后序遍歷

在Java的面試中，二叉樹的遍歷是一個常見的算法主題。本文將介紹一道經(jīng)典的Java面試題——二叉樹的后序遍歷，并提供詳細(xì)的解析和解題思路。

題目

給定一個二叉樹，按照后序遍歷的順序輸出節(jié)點的值。

解析與解題思路

二叉樹的后序遍歷是一種常見的樹遍歷方式，可以使用遞歸或迭代的方式來實現(xiàn)。

1. 遞歸解法：如果二叉樹為空，則返回。首先遞歸地后序遍歷當(dāng)前節(jié)點的左子樹。然后遞歸地后序遍歷當(dāng)前節(jié)點的右子樹。輸出當(dāng)前節(jié)點的值。
2. 迭代解法（使用棧）：創(chuàng)建一個棧，并將根節(jié)點入棧。初始化一個指針current指向根節(jié)點，用于記錄當(dāng)前訪問的節(jié)點。初始化一個指針lastVisited指向null，用于記錄上次訪問的節(jié)點。當(dāng)棧不為空時，重復(fù)以下步驟：將棧頂節(jié)點的左子樹依次入棧，直到左子樹為空。獲取棧頂節(jié)點，但不彈出。如果棧頂節(jié)點的右子樹為空，或者上次訪問的節(jié)點是棧頂節(jié)點的右子節(jié)點，則彈出棧頂節(jié)點并輸出其值，將lastVisited更新為棧頂節(jié)點。否則，將棧頂節(jié)點的右子節(jié)點入棧，并將current更新為棧頂節(jié)點的右子節(jié)點。

以下是Java代碼實例（使用遞歸解法）：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class PostorderTraversal {
    public static void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        postorderTraversal(root.left); // 遞歸地后序遍歷左子樹
        postorderTraversal(root.right); // 遞歸地后序遍歷右子樹
        System.out.print(root.val + " "); // 輸出當(dāng)前節(jié)點的值
    }

    public static void main(String[] args) {
        /*
         * 構(gòu)造二叉樹：
         *      1
         *     / \
         *    2   3
         *   / \
         *  4   5
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("后序遍歷結(jié)果：");
        postorderTraversal(root);
    }
}

輸出結(jié)果：

后序遍歷結(jié)果：4 5 2 3 1

結(jié)論 

通過遞歸或迭代的方式，我們可以實現(xiàn)二叉樹的后序遍歷。掌握了解題思路和實現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

學(xué)java，就到java編程獅！