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

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

題目

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

解析與解題思路

二叉樹的層序遍歷是一種廣度優(yōu)先搜索（BFS）的應(yīng)用，可以使用隊列來實現(xiàn)。

1. 創(chuàng)建一個隊列，并將根節(jié)點(diǎn)入隊。
2. 當(dāng)隊列不為空時，重復(fù)以下步驟：彈出隊首節(jié)點(diǎn)，輸出其值。將彈出節(jié)點(diǎn)的左子節(jié)點(diǎn)入隊（如果存在）。將彈出節(jié)點(diǎn)的右子節(jié)點(diǎn)入隊（如果存在）。
3. 重復(fù)步驟2直到隊列為空。

以下是Java代碼實例：

import java.util.LinkedList;
import java.util.Queue;

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

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

public class LevelOrderTraversal {
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " "); // 輸出當(dāng)前節(jié)點(diǎn)的值

            if (node.left != null) {
                queue.offer(node.left); // 將左子節(jié)點(diǎn)入隊
            }

            if (node.right != null) {
                queue.offer(node.right); // 將右子節(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é)果：");
        levelOrderTraversal(root);
    }
}

輸出結(jié)果：

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

結(jié)論

 通過廣度優(yōu)先搜索（BFS）算法，我們可以實現(xiàn)二叉樹的層序遍歷。層序遍歷按照從上到下、從左到右的順序遍歷二叉樹的節(jié)點(diǎn)，是一種常見且重要的遍歷方式。掌握了解題思路和實現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

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