Leetcode Populating Next Right Pointers in Each Node II-CSDN博客

本文链接：https://blog.csdn.net/rosepicker/article/details/74551944

本文探讨了在常数额外空间限制下解决“填充每个节点的下一个右侧节点”问题的方法，特别是对于任意二叉树的情况。通过引入哨兵节点简化了代码实现，使解决方案更加简洁高效。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,
Given the following binary tree,

After calling your function, the tree should look like:

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

写代码时陷入了各种复杂情况的判断，写的举步维艰。后面参考了下别人的代码，发现通过使用哨兵节点，可以很大的简化复杂度，写简洁优雅代码真是技巧性的活。

代码如下：

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root)  
        {  
            TreeLinkNode* temp = new TreeLinkNode(0);
            TreeLinkNode* cur = temp;
            while(root)  
            {
                if(root->left != NULL)
                {
                    cur->next = root->left;
                    cur = cur->next;
                }
                if(root->right != NULL)
                {
                    cur->next = root->right;
                    cur = cur->next;
                }
                root = root->next;
            }  
            
            root = temp->next;
            temp->next = NULL;
            delete temp;
        }  
    }
};