给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
1.用一个队列来存储遍历到的元素。广度优先遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
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.offer(root);
while(!queue.isEmpty()){//队列中不为空,表示树未遍历完毕
List<Integer> subList = new ArrayList<>();
int size = queue.size();//记录这个层有几个元素
for(int i =0;i < size;i++){//从队列中取出该层的所有元素,加入subList
root = queue.poll();
subList.add(root.val);
if(root.left != null){//如果当前节点的左子树不为空,将左子节点加入队列
queue.offer(root.left);
}
if(root.right != null){//如果当前节点的右子树不为空,将右子节点加入队列
queue.offer(root.right);
}
}
list.add(subList);
}
return list;
}
}
2.迭代实现,深度优先遍历。
class Solution {
List<List<Integer>> list = new ArrayList<>();
//深度优先遍历,把每一个节点加入到对应层的列表中
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return list;
}
levelOrder(root,0);
return list;
}
//level表示层数
public void levelOrder(TreeNode node,int level){
if(list.size() == level){//当前层数和list的大小一样,就说明需要一个新的列表来存储当前层元素
list.add(new ArrayList<Integer>());//新建一个新的subList
}
list.get(level).add(node.val);//在当前层的subList中插入元素
if(node.left != null){//如果左子树不为空, 遍历左子树
levelOrder(node.left,level+1);
}
if(node.right != null){//如果右子树不为空,遍历右子树
levelOrder(node.right,level+1);
}
}
}
题源:力扣