題目:(vivo面試)
給你一個二叉樹,請你傳回其按 層序周遊 得到的節點值。 (即逐層地,從左到右通路所有節點)。
示例:
二叉樹:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
傳回其層次周遊結果:
[
[3],
[9,20],
[15,7]
]
題解:
import java.util.*;
class TreeNode {
int val;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//層序周遊用隊列
//邊界條件
List<List<Integer>> list = new ArrayList<>();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> subList = new ArrayList<>();//注意:新定義的subList一定要放到while裡面
int size = queue.size();//size是queue的size
for (int i = 0; i < size; i++) {
TreeNode temp = queue.poll();
subList.add(temp.val);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
list.add(subList);
}
return list;
}
}
public class Main {
public static void main(String[] args) {
TreeNode head = new TreeNode(1);//849
TreeNode second = new TreeNode(2);//850
TreeNode three = new TreeNode(3);//851
TreeNode four = new TreeNode(4);//852
TreeNode five = new TreeNode(5);//853
TreeNode six = new TreeNode(6);//854
TreeNode seven = new TreeNode(7);//855
head.right = three;
head.left = second;
second.right = five;
second.left = four;
three.right = seven;
three.left = six;
Solution s = new Solution();
List<List<Integer>> list = s.levelOrder(head);
System.out.println(list);
}
}