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

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

題目

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

解析與解題思路

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

1. 遞歸解法：如果二叉樹為空，則返回。首先遞歸地中序遍歷當(dāng)前節(jié)點(diǎn)的左子樹。輸出當(dāng)前節(jié)點(diǎn)的值。最后遞歸地中序遍歷當(dāng)前節(jié)點(diǎn)的右子樹。
2. 迭代解法（使用棧）：創(chuàng)建一個棧，并將根節(jié)點(diǎn)入棧。初始化一個指針current指向根節(jié)點(diǎn)。當(dāng)棧不為空或current不為空時，重復(fù)以下步驟：如果current不為空，將current入棧，將current更新為其左子節(jié)點(diǎn)。如果current為空，彈出棧頂節(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 InorderTraversal {
    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

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

    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é)果：");
        inorderTraversal(root);
    }
}

輸出結(jié)果：

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

結(jié)論

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

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