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

二叉树的层序遍历：利用循环不变式解决难点

问题描述

二叉树的层序遍历是一种常见的算法问题，通常使用队列来辅助实现。然而，题目中增加了一点难度：要求同一行的存储与同一vector中处理。在传统的实现中，可能会使用多个vector分别存储不同层的节点，这使得检查和处理同一行的节点略显麻烦。

挖掘问题难点

传统的实现方法中，处理每个节点时会单独检查左右子节点，并将子节点加入队列中。这样做的问题在于，靠近队列尾部的节点即将被处理，进而导致同一层的节点分散在不同的队列位置中。在这种情况下，如何保证同一层的节点能够被一次性处理，并存储在同一vector中，是当前问题的主要难点。

解决方法：循环不变式

为了解决这个难点，我们可以采用循环不变式的思想。循环不变式的具体实现是：在每次循环中，先计算当前队列中节点的数量count，然后将这些节点计数的大小批量处理一遍。每次处理后，将当前层的节点存入结果vector中，然后移除它们，处理它们的子节点并将子节点加入队列中。

这种方法的优点在于，保证了每次循环处理的都是同一层的节点，从而能够将同一层的节点一次性存储到同一个vector中。这使得过程清晰，逻辑严谨，同时也简化了代码的编写和维护。

代码实现

#include 
   
    #include 
    
     using namespace std;class Solution {    public:        vector
     
      
       > levelOrder(TreeNode* root) {            vector
       
        
         > ans; if (root == NULL) return ans; queue
         
           Q; Q.push(root); while (!Q.empty()) { int count = Q.size(); ans.push_back(vector
          
           ()); for (int i = 0; i < count; ++i) { TreeNode* temp = Q.front(); Q.pop(); ans.back().push_back(temp->val); if (temp->left) Q.push(temp->left); if (temp->right) Q.push(temp->right); } } return ans; }};
          
         
        
       
      
     
    
   

运行结果

层序遍历的结果将被逐层存储在ans这个二维vector中。每次循环处理一层节点后，就将他们的值添加到结果中，然后将左、右子节点加入队列中。这种方法确保了每一层的节点都被正确地存入同一个vector中，从而满足了题目的要求。