利用循环不变式实习二叉树的层序遍历(LeetCode 102)

àì夳堔傛蜴生んèń 2022-12-19 06:23 57阅读 0赞

一、问题描述(二叉树的层序遍历)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]

> 这道题增加的一点点难度体现在要求同一行存储与同一vector中

二、利用**循环不变式**解决这一个小难点  
所谓循环不变式，结合本题的场景，通俗理解就是：  
**一次性处理同一层，则可以使队列中永远是同一层的结点。**  
比如：3处理完后，队列里有9、20这两个结点的地址(指针)，一次性把这2个结点处理了，队列里得到的是15、7这两个结点的地址，即保证了队列中永远是同一层的结点。

严谨证明，见：[含循环不变式的证明][Link 1]

三、AC代码如下

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            vector<vector<int> > ans;
            if(root == NULL) return ans;
            queue<TreeNode *> Q;
            Q.push(root);
            while(!Q.empty()) {
        
                int count = Q.size();
                ans.push_back(vector<int>()); //将一维空vector插入
                for(int i = 0; i < count; i++) {
        
                    auto temp = Q.front(); Q.pop();
                    ans.back().push_back(temp->val); //同一行存储与同一vector中
                    if(temp->left) Q.push(temp->left);
                    if(temp->right) Q.push(temp->right);
                }
            }
            return ans;
        }
    };

四、运行结果  
![在这里插入图片描述][20201105225025117.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7811f087c9fe45708f843e550acfe80b.png
[Link 1]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
[20201105225025117.png_pic_center]: https://img-blog.csdnimg.cn/20201105225025117.png#pic_center