在Java的面試中,二叉樹的遍歷是一個常見的算法主題。本文將介紹一道經(jīng)典的Java面試題——二叉樹的層序遍歷,并提供詳細(xì)的解析和解題思路。
題目
給定一個二叉樹,按照層序遍歷的順序輸出節(jié)點(diǎn)的值。
解析與解題思路
二叉樹的層序遍歷是一種廣度優(yōu)先搜索(BFS)的應(yīng)用,可以使用隊(duì)列來實(shí)現(xiàn)。
- 創(chuàng)建一個隊(duì)列,并將根節(jié)點(diǎn)入隊(duì)。
- 當(dāng)隊(duì)列不為空時,重復(fù)以下步驟:彈出隊(duì)首節(jié)點(diǎn),輸出其值。將彈出節(jié)點(diǎn)的左子節(jié)點(diǎn)入隊(duì)(如果存在)。將彈出節(jié)點(diǎn)的右子節(jié)點(diǎn)入隊(duì)(如果存在)。
- 重復(fù)步驟2直到隊(duì)列為空。
以下是Java代碼實(shí)例:
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)入隊(duì)
}
if (node.right != null) {
queue.offer(node.right); // 將右子節(jié)點(diǎn)入隊(duì)
}
}
}
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)算法,我們可以實(shí)現(xiàn)二叉樹的層序遍歷。層序遍歷按照從上到下、從左到右的順序遍歷二叉樹的節(jié)點(diǎn),是一種常見且重要的遍歷方式。掌握了解題思路和實(shí)現(xiàn)代碼,我們能夠在面試中更加自信地回答相關(guān)問題。
學(xué)java,就到java編程獅!