LeetCode 题解：Populating Next Right Pointers in Each Node I & II 二有难度。考虑不全面。

每次应该把root同层的右侧节点传过来。如果没有，就传NULL。

同时，应该是先右后左。

感觉这次的代码还挺简洁的。。

void construct(struct TreeLinkNode *root, struct TreeLinkNode *r_brother)

{

    if(root == NULL)    return;

    root->next = r_brother;

    construct(root->right,r_brother == NULL ? NULL : r_brother->left);

    construct(root->left, root->right);

}

void connect(struct TreeLinkNode *root) {

    construct(root,NULL);

}

题目II，第一次提交错了。因为r_brother本身没有儿子，而他右侧又有儿子的情况，没有考虑到。

比如下图中的 7 节点，因为5没有儿子，按照之前的逻辑，7也没有右兄弟。

这时应该怎么办呢？

应该沿着5，向右挨个询问，直到最右，都没有儿子，才死心。

void construct(struct TreeLinkNode *root, struct TreeLinkNode * r_brother)

{

    if(root == NULL)    return;

    root->next = r_brother;

    struct TreeLinkNode * new_r_brother = NULL;

    while(r_brother != NULL)

    {

        new_r_brother = r_brother->left == NULL ? r_brother->right : r_brother->left;

        if(new_r_brother)   break;

        r_brother = r_brother->next;

    }

    if(root->right)

    {

        construct (root->right, new_r_brother);

        new_r_brother = root->right;

    }

    construct(root->left, new_r_brother);

}

void connect(struct TreeLinkNode *root) {

    construct(root,NULL);

}

巴特西

LeetCode 题解：Populating Next Right Pointers in Each Node I & II 二有难度。考虑不全面。

最新文章

热门文章