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

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

題目

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

解析與解題思路

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

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

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

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é)點(diǎn)的值
    }

    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é)論 

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

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