c++ - 二叉树的层序遍历

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()进入 res，此函数的返回值。

错误出现在这段代码中:

        ptr = q.front();
        q.pop();

        if(q.empty())
            break;

这会从队列中移除下一个元素。如果元素被移除后队列为空，则算法终止。

此处的意图是队列中最后的、最终的、剩余的值始终是树中最低级别最后一个值末尾的 NULL 指针。队列现已完全耗尽，算法终止。

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

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

push_back() 永远不会在树的底层执行。此函数的最终结果永远不会包括二叉树中的最低层。

将终止条件更改为:

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