水平顺序输出二叉树
给定一个二叉树，逐行输出二叉树中的每个节点
如：二叉树[1,2,3,4,5,6] 输出：[[1],[2,3],[4,5,6]]
沿着二叉树的某一个路径遍历，一直到达路径最末端。然后继续遍历其他路径，直到所有路径遍历完成为止。
本题，我们可以使用二叉树的前序遍历实现。
public List<List<Integer>> solution(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
return traverTree(root, 0, ret);
}
Map<Integer, List<Integer>> hash = new HashMap<>();
/**
* 先序遍历 其实三种树的遍历都是能实现的
*/
public void traverTree(TreeNode node, int depth, List<List<Integer>> ret) {
// 遍历到路径最深度，直接返回
if(node == null) {
return;
}
List<Integer> levelRet = hash.get(depth);
if(levelRet == null) {
levelRet = new ArrayList<>();
levelRet.add(node.val);
// 放入hash桶和结果列表
ret.add(levelRet);
hash.put(depth, levelRet);
}
traverTree(node.left, depth + 1, ret);
traverTree(node.right, depth + 1, ret);
}
广度优先，就是逐行输出二叉树每一层的节点值。上一层输出结束继续输出下一层。
这道题，可以使用栈来实现树的广度优先遍历。
public List<List<Integer>> solution(TreeNode root) {
Queue<TreeNode> nodes = new LinkedList<>();
nodes.add(root);
List<List<Integer>> ret = new ArrayList<>();
// 遍历每一层
while(!nodes.isEmpty()) {
List<Integer> vals = new ArrayList<>();
// 遍历当前层
for(int i = 0; i < nodes.size(); i++){
TreeNode node = nodes.poll();
vals.add(node.val);
if(node.left != null) {
nodes.add(node.left);
}
if(node.right != null) {
nodes.add(node.right);
}
}
}
}