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

题目

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

思路

一个队列解决，算法好像叫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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！