【每日一题】JZ22 从上往下打印二叉树

当你的才华还撑不起你的野心时，你应该静下心去学习 。 题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

输入

    3
   / \
  9  20
    /  \
   15   7

输出

[3,9,20,15,7]

解题思路

1. 特例处理： 当树的根节点为空，则直接返回空列表 [] ；

2. 初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；

3. BFS 循环： 当队列 queue 为空时跳出；

   • 出队： 队首元素出队，记为 node；
   • 打印： 将 node.val 添加至列表 tmp 尾部；
   • 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；

4. 返回值： 返回打印结果列表 res 即可。

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

参考代码 Java版本

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue queue = new LinkedList(){{ add(root); }};
        ArrayList ans = new ArrayList();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i val);
            if(node->left)
                q.push(node->left);
            if(node->right)
                q.push(node->right);
        }
        return res;

    }
}
// 关注TechGuide，大厂笔经面经闪电速递！

创作不易，你的鼓励是我创作的动力，如果你有收获，点个赞吧👍