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

Question

我正试图在C.中的Leetcode上解决这个问题

给定以下二叉树，

     1
   /  
  2    3
 /     
4   5    7

调用函数后，树应该看起来像：

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

我正在做的是为树的Level Order Traversal创建一个队列并将每个节点的下一个指针连接到每个数量为了分隔级别，我将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);
}

我现在还不能真正测试它，所以它可能不会直接工作，它主要是为了这个想法。

Answer 2

我会在javascript中提供我的结果，但我会提供足够的解释，说明用另一种语言重现这一结果的步骤：

1. 使用level order traversal (breadth-first search)来处理这个问题
2. 检查提供的根是否为null，如果为null，我们将立即返回
3. 创建一个queue，用于存储二叉树节点
4. 将根目录推入队列
5. 启动一个while循环，该循环仅在队列中有项目时运行
6. 获取队列的长度并将其存储在变量中，例如queueLength
7. 循环通过队列的长度（queueLength），同时观察循环的当前索引
8. 移位/移除queue中index 0上的项目并将其保存为currValue
9. 首先检查它是否有左节点，如果有则将其推入队列
10. 检查它是否也有节点值，如果有则将其推入队列
11. 如果循环中索引的值不等于queueLength-1，则currValue.next将等于queue[0]，即队列上的第一个项目
12. 如果循环中索引的值等于queueLength-1，那么这是该级别上的最后一个节点，我们可以将其下一个值设置为null
13. while循环将再次重复step 6 - 12

const connect = function (root) {
    let queue = [];
    
    if(root){
        queue.push(root);
    }
    while (queue.length) {
        // let curr = queue.shift(1);
        const queueLength = queue.length;
        for (let i = 0; i < queueLength; i++) {
            const currValue = queue.shift(0);
            if (currValue.left) {
                queue.push(currValue.left);
            }
            if (currValue.right) {
                queue.push(currValue.right);
            }
            if (i !== queueLength - 1) {
                currValue.next = queue[0];
            }
            if (i === queueLength - 1) {
                currValue.next = null;
            }
        }
    }
    return root;
};