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

层序遍历

单层向量实现

思路

层序遍历是一种常见的树遍历方式，通常用于前序、后序或层序访问树节点。以下是实现层序遍历的单层向量方法。

解法

该方法通过队列来控制节点的访问顺序。具体步骤如下：

代码示例

#include 
   
    #include 
    
     using namespace std;vector
     
       levelOrder(TreeNode* root) {    if (root == nullptr) return {};    vector
      
        res;    queue(TreeNode*> my_queue;    my_queue.push(root);    while (!my_queue.empty()) {        int size = my_queue.size();        vector
       
         tmp;        while (size--) {            TreeNode* cur = my_queue.front();            my_queue.pop();            tmp.push_back(cur->val);            if (cur->left) my_queue.push(cur->left);            if (cur->right) my_queue.push(cur->right);        }        res.push_back(vector
        
         (tmp.rbegin(), tmp.rend())); } return res;}
        
       
      
     
    
   

双层向量实现

思路

该方法与单层向量实现类似，但每次遍历时将当前层的节点值倒序存储到结果向量中。

解法

代码示例

#include 
   
    #include 
    
     using namespace std;vector
     
      
       > levelOrder(TreeNode* root) {    if (root == nullptr) return {};    vector
       
        
         > res; queue
         
           my_queue; my_queue.push(root); bool reverse = false; while (!my_queue.empty()) { int size = my_queue.size(); vector
          
            tmp; while (size--) { TreeNode* cur = my_queue.front(); my_queue.pop(); tmp.push_back(cur->val); if (cur->left) my_queue.push(cur->left); if (cur->right) my_queue.push(cur->right); } if (reverse) { res.push_back(vector
           
            (tmp.rbegin(), tmp.rend())); } else { res.push_back(tmp); } reverse = !reverse; } return res;}
           
          
         
        
       
      
     
    
   

之字型双层向量实现

思路

该方法通过在层序遍历中每层交替倒序和正序存储节点值，形成之字型的结果。

解法

代码示例

#include 
   
    #include 
    
     using namespace std;vector
     
      
       > levelOrder(TreeNode* root) {    if (root == nullptr) return {};    vector
       
        
         > res; queue
         
           my_queue; my_queue.push(root); bool reverse = false; while (!my_queue.empty()) { int size = my_queue.size(); vector
          
            tmp; while (size--) { TreeNode* cur = my_queue.front(); my_queue.pop(); tmp.push_back(cur->val); if (cur->left) my_queue.push(cur->left); if (cur->right) my_queue.push(cur->right); } if (reverse) { res.push_back(vector
           
            (tmp.rbegin(), tmp.rend())); } else { res.push_back(tmp); } reverse = !reverse; } return res;}
           
          
         
        
       
      
     
    
   

这些方法通过队列和向量巧妙地控制了树节点的遍历顺序，实现了层序遍历的不同风格。