题目描述
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ]
思路
1.使用队列存储结点,方便层级遍历。
2.使用count,curMax分别表示该层当前遍历结点的个数和该层总结点的个数。
3.当count==curMax的时候,说明这层结点遍历完成,进行一系列初始化操作即可。
Java代码实现
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); LinkedList<TreeNode> nodes = new LinkedList<>(); List<Integer> curVals = new ArrayList<>(); int curMax = 1; int count = 0; if(root != null) nodes.add(root); while(!nodes.isEmpty()){ TreeNode cur = nodes.pollFirst(); curVals.add(cur.val); count++; if(cur.left != null) nodes.add(cur.left); if(cur.right != null) nodes.add(cur.right); //进行一系列的初始化操作 if(count == curMax){ curMax = nodes.size(); count = 0; res.add(curVals); curVals = new ArrayList<>(); } } return res; }