【LeetCode 精选TOP】剑指 Offer 32 - I. 从上到下打印二叉树

本是古典何须时尚 2022-11-08 14:20 111阅读 0赞

# 剑指 Offer 32 - I. 从上到下打印二叉树 #

## 一、题目 ##

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

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

![f824fdd8052ae4ee657365c98633480caf03c60e42e4661797618e318baf8664-Picture0.png][]

## 二、解题思路 ##

根据题目要求"从上到下打印"，且“同一层的节点从左到右”，了解这题考察的方向是**二叉树的层次遍历**。

> 二叉树的遍历方式常见的有四种，分别是
> 
>  *  先序遍历
>  *  中序遍历
>  *  后序遍历
>  *  层序遍历

接下来，我们需要记住**层序遍历通常是借助队列来实现**。

具体思路是：

*  首先判断边界条件：如果根节点为空，直接返回空列表
 *  根节点不为空时，将根节点入队
 *  while 队列不为空
    
     *  获取队首元素node，并出队
     *  将node的值加入最终输出列表
     *  判断node 左子节点是否为空，若不为空，则入队
     *  判断node 右子节点是否为空，若不为空，则入队
 *  返回最终输出列表

**C++ 代码实现**

class Solution {
    public:
        vector<int> levelOrder(TreeNode* root) {
            
            std::vector<int> result;
            // 边界条件判断
            if(!root){
                return result;
            }
    
            queue<TreeNode*> q;
            q.push(root);
            while(!q.empty()){
                TreeNode* node = q.front();
                q.pop();
                result.emplace_back(node->val);
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
            return result;
        }
    };

## 三、知识扩展 ##

在本题中主要涉及到了C++标准库中队列的使用。下面对C++ 队列的常用方法进行总结。

### 3.1 队列的特点 ###

*  队列与栈一样，是一种线性存储结构
 *  遵循“先进先出”的原则。在队尾添加元素，称为入队；在队首删除元素，称为出队。

### 3.2 队列的常用操作 ###

*  入队
 *  出队
 *  获取队首元素
 *  获取队尾元素
 *  获取队列元素个数
 *  判断队列是否为空

### 3.3 C++ 标准库中队列的使用 ###

*  首先引入头文件
    
        #include<queue>
 *  队列的定义
    
        queue<T> q;  // 其中T为int，char,float等
 *  常用函数
    
        q.push(e)               在队尾压入新元素e
        q.pop()                 弹出队首元素，无返回值
        q.front()               获取队首元素
        q.back()                获取队列尾元素
        q.size()                返回队列中元素个数
        q.empty()               判断队列是否为空

[f824fdd8052ae4ee657365c98633480caf03c60e42e4661797618e318baf8664-Picture0.png]: /images/20221023/16fce8f0b3a44e9f94b19ad10a0aad29.png