c - 填充二叉树的每个节点中的下一个右指针

Question

我正在尝试做this problem on Leetcode在 C 中。

给定以下二叉树，

     1
   /  \
  2    3
 / \    \
4   5    7

调用函数后，树应如下所示:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

我正在做的是为树的级别顺序遍历创建一个队列 并将每个节点的下一个指针连接到每个队列的下一个节点 等级。为了分隔级别，我将 NULL 指针排入队列。

所以对于上面的例子::队列是-> [1,#, 2,3,#,4,5,7,#] 其中 # 是 NULL ptr。

这是我的问题代码::

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
bool isEmpty(int start,int end){
    if(start > end)
        return true;
    return false;
}

void connect(struct TreeLinkNode *root) {
    if(!root || (!root->left && !root->right))
        return;
    int cap = 1000;
    struct TreeLinkNode** q = malloc(cap* sizeof(struct TreeLinkNode*));
    int start=0, end=-1, curLevel=1, nextLevel=0;
    // enqueue
    q[++end] = root;
    while(isEmpty(start, end) == false){
        //dequeue
        struct TreeLinkNode* temp = q[start++];
        curLevel--;
        if(isEmpty(start, end) == false && curLevel !=0)
            temp->next = q[start];
        if(temp->left){
            q[++end] = temp->left;
            nextLevel++;
        }
        if(temp->right){
            q[++end] = temp->right;
            nextLevel++;
        }
        if(curLevel ==0){
            curLevel = nextLevel;
            nextLevel =0;
        }
        if(start> cap-50 || end> cap-50)
            q = realloc(q, 2*cap*sizeof(struct TreeLinkNode *));
    }
    free(q);
}

该代码显然适用于小型测试用例，但对于 Leetcode 上的较大测试用例，该代码会给出运行时错误。 我不知道我做错了什么。 请帮忙。如果有人可以在 Leetcode 上运行此代码，我将非常感激

Answer 1

当您分析上一关卡的最后一个节点时，关卡就结束了。由于q中每个级别都以NULL结尾，因此当temp为NULL时，意味着整个级别已被分析，您可以通过插入NULL来结束下一个级别。

所以我对您的代码做了一些修改:

void connect(struct TreeLinkNode *root) {
    int cap = 1000;
    struct TreeLinkNode** q = malloc(cap* sizeof(struct TreeLinkNode*));
    int start=0, end=-1;
    // enqueue
    q[++end] = root;
    q[++end] = NULL; // End of first level
    for (;;) {
        //dequeue
        struct TreeLinkNode* temp = q[start++];
        if (temp == NULL) {
            if (q[start] == NULL) // Two consecutives NULL means end of tree
                break;
            q[++end] = NULL; // End of level
        } else {
            temp->next = q[start];
            if(temp->left)
                q[++end] = temp->left;
            if(temp->right)
                q[++end] = temp->right;
            if (end > cap-50) { // end is always greater or equal to start
                q = realloc(q, 2*cap*sizeof(struct TreeLinkNode *));
            }
        }
    }
    free(q);
}

我现在无法实际测试它，所以它可能无法直接工作，主要是为了这个想法。