二进制树的水平顺序遍历

Question

我正在编写二进制树的C 函数，

但不是打印所有级别，有人可以告诉这个代码有什么问题？这是我的代码：##

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector< vector<int> > res;
        TreeNode* ptr;
        queue<TreeNode*> q;
        vector<int> v;            
        if(root){
            q.push(root);
            q.push(NULL);
        }
        while(!(q.empty())){
            ptr = q.front();
             q.pop();
            if(q.empty())
                break;
            if(ptr){
                    if(ptr->left)
                        q.push(ptr->left);
                    if(ptr->right)
                        q.push(ptr->right);
                    v.push_back(ptr->val);
                }
            else {
                    q.push(NULL);
                    res.push_back(v);
                    v.clear();
                }                                    
        }            
        return res;                              
    }
};

Answer 1

总结此代码中的总体逻辑：

1）保持队列，每个级别的节点都被推入每个级别，然后在每个级别上的最后一个元素之后按NULL指针。该算法通过将根元素推入队列开始，然后将根元素推入NULL。

2）每个级别的元素都会从队列中弹出，然后将其重新推回了队列。

3）当NULL指针从队列上弹出时，这一定意味着队列不包含下一个级别的元素，因此NULL立即将其推回了队列。

4）代码首先将队列中的所有元素收集到临时缓冲区v中。当NULL指针从队列中弹出时，v现在包含二进制树中单个级别上的所有元素，并且v将push_back() ED添加到res中，从此函数中返回值。

该错误发生在代码的这一部分中：

        ptr = q.front();
        q.pop();
        if(q.empty())
            break;

这将从队列中删除下一个元素。该算法终止如果队列为空删除了元素。

这里的目的是，队列中的最后一个最终值始终是在树中最低级别上最后一个值结束时的NULL指针。队列现在已完全排干，算法终止。

不幸的是，该算法已从v向量中的树中最低级别收集了所有值，并且保存它们的代码的以下部分已完全跳过：

                q.push(NULL);
                res.push_back(v);
                v.clear();

push_back()永远不会在树中的底层执行。该功能的最终结果将永远不会包括二进制树中的最低水平。

将终止条件更改为：

        if(q.empty())
        {
            res.push_back(v);
            break;
        }