剑指 Offer 32 - II: 从上到下打印二叉树 II

[songyy5517]

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

分析 这道题考察的是二叉树的层次遍历（BFS），关键是区分二叉树每行的节点。因此我们还是可以基于队列对二叉树进行层次遍历。为了区分不同行的节点，我们可以根据队列的当前容量确定下一层的节点数，从而依次取出节点即可。

[songyy5517]

思路：根据队列当前容量打印每层节点

1. 异常处理；
2. 定义队列queue和结果列表res，将根节点添加到队列中；
3. 层次遍历（BFS）：当队列不为空时： （1）获取队列的当前容量 size； （3）定义并初始化每层列表row； （2）内层循环size次：
   • 从队列中取出当前节点，并添加到每层列表row中；
   • 若节点存在左右子节点，则将子节点也添加到队列尾部； （3）将该层列表添加到结果列表中；
4. 返回结果列表res。

复杂度分析

• 时间复杂度： $O(N)$ ， $N$ 为二叉树的节点数，我们需要对二叉树中的每个节点进行遍历。
• 空间复杂度： $O(N)$ ，额外定义了 $O(N)$ 大小的队列。

[songyy5517]

/** 12:50-13:13
 * 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>> decorateRecord(TreeNode root) {
        // 思路：重点在于区分每行，我们可以额外定义一个标识符'-1'用于区分每行的节点
        // 1. 异常处理
        if (root == null)
            return new ArrayList<>();

        // 2. 定义相关变量
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> row = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        // 3. 层次遍历二叉树
        while (!queue.isEmpty()){
            // 获取每行的节点数
            int num = queue.size();
            row = new ArrayList<Integer>();

            for (int i = 0; i < num; i++){
                TreeNode cur = queue.remove();
                row.add(cur.val);
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }

            res.add(row);
        }

        return res;
    }
}

[songyy5517]

2023/1/26 2023/1/28 2024/1/28

• 抽象类List的实例化