LeetCode-面试题32-2-从上到下打印二叉树

题目

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

​ 3 /
9 20 /
15 7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

1. 节点总数 <= 1000

解题思路

方法1：递推

依然是BFS，只是要多2个List去保存结果，还需要2个变量一个记录下一层的节点数目，另一个记录当前层没有打印的节点数目

用一个队列Queue保存节点，标准BFS遍历模版如下：

• 将root节点放入queue，当前待打印节点数-1

• 重复以下2个步骤，直到queue为空为止：

  取出queue中的头结点，添加进rowList中

  找出头结点左右子节点，依次放入queue中，下一行节点数目+1

  当前行待打印节点数==0时，说明这行节点都添加进了rowList中，将rowList添加进result，进入下一行，当前行=下一行节点数，下一行节点数清空，rowList清空，这里不能用list.clear()方法，这个方法会把对应的引用数据清掉，直接new ArrayList()即可

方法2：递归

初始化一个k作为树层数标记，对于大的list而言，每一层都是一个小list，当这个小list没有时，新建这个小list添加进头结点（大list的长度<=k）

如果存在这一层的小list，就在这个小list中继续添加这一层的数据即res[depth].append(node.val)

之后进行头结点左子树和右子树的递归，每一次递归层数+1即

• traversal(node.left, depth + 1)
• traversal(node.right, depth + 1)·

Java代码

/**
 * 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) {
        if(root==null) return new ArrayList();
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> row = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int rownode = 1;
        int nextrow = 0;
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            row.add(temp.val);
            if(temp.left!=null){
                queue.add(temp.left);
                nextrow++;
            }
            if(temp.right!=null){
                queue.add(temp.right);
                nextrow++;
            }
            rownode--;
            if(rownode==0){
                result.add(row);
                rownode = nextrow;
                nextrow = 0;
                row = new ArrayList();
            }
        }
        return result;
    }
}

Python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        def traversal(node, depth):
            if not node:
                return
            if len(res) <= depth:  # 如果结果集没有对应层数的列表，则先创建并将当前节点值压入
                temp = []
                temp.append(node.val)
                res.append(temp)
            else:  # 如果有，直接压入对应层数所对应的列表
                res[depth].append(node.val)
            traversal(node.left, depth + 1)
            traversal(node.right, depth + 1)
        traversal(root, 0)
        return res