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

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

題目

給定一個(gè)二叉樹，按照前序遍歷的順序輸出節(jié)點(diǎ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)入棧。當(dāng)棧不為空時(shí)，重復(fù)以下步驟：彈出棧頂節(jié)點(diǎn)，輸出其值。如果當(dāng)前節(jié)點(diǎn)有右子樹，將右子樹入棧。如果當(dāng)前節(jié)點(diǎn)有左子樹，將左子樹入棧。

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

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

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

public class PreorderTraversal {
    public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val + " "); // 輸出當(dāng)前節(jié)點(diǎn)的值
        preorderTraversal(root.left); // 遞歸地前序遍歷左子樹
        preorderTraversal(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é)果：");
        preorderTraversal(root);
    }
}

輸出結(jié)果：

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

結(jié)論

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

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