本文共 2928 字，大约阅读时间需要 9 分钟。

题目

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

思路

一个队列解决，算法好像叫BFS。

• 打印结果列表 ret = [] ，包含根节点的队列 queue = [root] ；
• 循环： 当队列 queue 为空时跳出；
  • 出队： 队首元素出队，记为 node；
  • 打印： 将 node.val 添加至列表 ret 尾部；
  • 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
• 返回打印结果列表即可。

代码

/** * Definition for a binary tree node. * struct TreeNode { *
 int val; *
 TreeNode *left; *
 TreeNode *right; *
 TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:
vector
   
     levelOrder(TreeNode* root) {
    
vector
    
      ret;
     
if(root == NULL){
     
return ret;
     
}
     
queue
     
       q;
      
q.push(root);
      
while(q.empty() != true){
      
TreeNode* p = q.front();
      
ret.push_back(p->val);
      
if(p->left != NULL) q.push(p->left);
      
if(p->right != NULL) q.push(p->right);
      
q.pop();
      
}
      
return ret;
      
}};
     
    
   

变体1

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

思路

• 打印结果列表 ret = [] ，包含根节点的队列 queue = [root] ；
• 循环： 当队列 queue 为空时跳出；
  • 循环次数为队列 queue 长度（队列中元素为所有当前层节点）
    • 出队： 队首元素出队，记为 node；
    • 打印： 将 node.val 添加至列表 ret 尾部；
    • 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
  • 将当前层结果 tmp 添加入 ret
• 返回打印结果列表即可。

代码

/** * Definition for a binary tree node. * struct TreeNode { *
 int val; *
 TreeNode *left; *
 TreeNode *right; *
 TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:
vector
   
    
     > levelOrder(TreeNode* root) {
     
vector
     
      
       > ret;
       
if(root == NULL){
       
return ret;
       
}
       
 queue
       
         q;
        
q.push(root);
        
while(q.empty() != true){
        
int sum = q.size();
        
vector
        
          tmp;
         
for(int i = 0;i < sum;i++){
         
TreeNode* p = q.front();
         
tmp.push_back(p->val);
         
if(p->left != NULL) q.push(p->left);
         
if(p->right != NULL) q.push(p->right);
         
q.pop();
         
}
         
ret.push_back(tmp);
         
tmp.clear();
         
}
         
 return ret;
         
}};
        
       
      
     
    
   

变体2

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

思路

用一个双向队列，偶数时取前往后放，奇数时取后往前放。

代码

/** * Definition for a binary tree node. * struct TreeNode { *
 int val; *
 TreeNode *left; *
 TreeNode *right; *
 TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:
vector
   
    
     > levelOrder(TreeNode* root) {
     
vector
     
      
       > ret;
       
if(root == NULL){
       
return ret;
       
}
       
 deque
       
         q;
        
q.push_back(root);
        
int k = 1;
        
while(q.empty() != true){
        
int sum = q.size();
        
vector
        
          tmp;
         
for(int i = 0;i < sum;i++){
         
TreeNode* p;
         
if(k % 2 == 0){
         
// 前取后放：从左向右打印，所以从前边取，后边放入
         
p = q.front();
         
q.pop_front();
         
if(p->right != NULL) q.push_back(p->right);// 下一层顺序存放至尾
         
if(p->left != NULL) q.push_back(p->left);
         
}else{
         
//后取前放： 从右向左，从后边取，前边放入
         
p = q.back();
         
q.pop_back();
         
if(p->left != NULL) q.push_front(p->left);// 下一层逆序存放至首
         
if(p->right != NULL) q.push_front(p->right);
         
}
         
tmp.push_back(p->val);
         
}
         
ret.push_back(tmp);
         
tmp.clear();
         
k++;
         
}
         
 return ret;
         
}};
        
       
      
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105642211 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！