二叉樹的層序遍歷
題目
給你一個二叉樹诵棵，請你返回其按 層序遍歷 得到的節(jié)點值。 （即逐層地掸绞，從左到右訪問所有節(jié)點）继找。
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)负溪，非商業(yè)轉(zhuǎn)載請注明出處透揣。
思路
因為是按層序遍歷,所以需要有標識來標識出當前節(jié)點的層級.而二叉樹的遍歷一般就是遍歷和遞歸兩種方式,所以在遞歸中將子節(jié)點的層級加1即可.對于返回數(shù)組大小和層級關(guān)系,當返回數(shù)組大小和層級相等時,則說明這是一個新的層級,需要創(chuàng)建新的隊列.
代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root){
List<List<Integer>> result = new ArrayList<>();
levelOrder(result,0,root);
return result;
}
private void levelOrder(List<List<Integer>> result,int level,TreeNode node){
if (node == null){
return;
}
if (result.size() == level){
List<Integer> list = new ArrayList<>();
list.add(node.val);
result.add(list);
}else{
result.get(level).add(node.val);
}
levelOrder(result,level+1,node.left);
levelOrder(result,level+1,node.right);
}
}
