在二叉树的每个节点中填充下一个右指针 [英] Populating Next Right Pointers in Each Node of a binary tree

问题描述

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

I am trying to do this problem on Leetcode in C.

给定以下二叉树，

     1
   /  \
  2    3
 / \    \
4   5    7

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

After calling your function, the tree should look like:

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

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

What I am doing is creating a queue for Level Order Traversal of the tree and joining the next pointer of each node to the next queue node at each level. To separate levels, I am enqueuing NULL pointer.

所以对于上面的例子::队列是->[1,#, 2,3,#,4,5,7,#] 其中 # 为空指针.

So for above example:: the queue is -> [1,#, 2,3,#,4,5,7,#] where # is 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 上运行此代码，我将不胜感激

the code is apparently working for small test cases but for larger ones on Leetcode the code gives runtime errors. I dont know what i am doing wrong. Please help. I would really appreciate if someone could run this code on Leetcode

推荐答案

我会在 javascript 中提供我的结果，但我会提供足够的解释来用另一种语言重现它的步骤:

I would be providing my result in javascript, but I would provide enough explanation on the steps to reproduce this in another language:

1. 使用层序遍历(广度优先搜索)来解决这个问题.
2. 检查提供的根是否为空，如果是，我们立即返回
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.

1. Approach this problem using level order traversal (breadth-first search).
2. Check if the provided root is null, if it is, we return it immediately
3. Create a queue that we would be using to store our binary tree nodes
4. Push the root into the queue
5. Start a while loop that would run only when there are items in the queue
6. Get the length of the queue and store it in a variable e.g. queueLength
7. loop through the length of the queue (queueLength) while observing the current index of the loop;
8. Shift/Remove the item on index 0 in the queue and save it as currValue
9. Check if it has a left node first, push it into the queue if it does
10. Check if it has a node value also, push it into the queue if it does
11. If the value of the index in the loop is not equal to queueLength-1, currValue.next would be equal to queue[0] i.e. the first item on the queue.
12. If the value of the index in the loop is equal to queueLength-1, then this is the last node on this level, we can set it's next value to null
13. The while loop would repeat step 6 - 12 again.

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;
};

这篇关于在二叉树的每个节点中填充下一个右指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！