题目链接：Populating Next Right Pointers in Each Node II

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,

         1 
       /  \ 
      2    3 
     / \  / \ 
    4  5  6  7

After calling your function, the tree should look like:

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

这道题的要求是补充二叉树中的next指针，即指向右边节点的指针。

和Populating Next Right Pointers in Each Node同样，其实是这个更针对一般情况一些。

注意到next其实就是指向广度优先搜索时的下一节点（同一层的），因此可以采用广度优先搜索，然后逐个赋值next指针，不过这样的空间复杂度为O(n)。

要想达到O(1)的空间复杂度，就需要巧妙的利用上next指针。大体思路是，利用前面一层已经赋值好的next指针，就可以从左到右地遍历上一层的节点，同时在遍历的时候，就可以对当前的节点建立基于next的连接。

对于每层节点，首先找到其下层的第一个节点，记录在f中，便于在改层结束时可以方便找到下一层；接下来，如果当前节点的left或者right不为NULL，说明遇到下一层的节点了，记录在l中，接着再按顺序找到一个下一层的节点，就可以令l的next指向下一个节点即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution
{
public:
    void connect(TreeLinkNode *root)
    {
        TreeLinkNode *p, *f = root;
        while(f != NULL)
        {
            // 找到下层的第一个非空节点，用f记录下来
            for(p = f; p != NULL; p = p -> next)
                if((f = p -> left) != NULL || (f = p -> right) != NULL)
                    break;
            
            while(p != NULL)
            {
                if(p -> left != NULL || p -> right != NULL)
                {
                    TreeLinkNode *l, *rr;
                    // 如果左右子树均非空，则令左子节点的next指向右子节点
                    if(p -> left != NULL)
                        l = p -> left, l -> next = p -> right;
                    if(p -> right != NULL)
                        l = p -> right, l -> next = NULL;
                    // 接着找到下一个子节点
                    for(p = p -> next; p != NULL; p = p -> next)
                        if((l -> next = p -> left) != NULL || (l -> next = p -> right) != NULL)
                            break;
                }
                else
                    p = p -> next;
            }
        }
    }
};

可以注意到，带有next指针的二叉树，每行都是一个链表，因此，同样可以利用处理链表时加个空头的技巧，这样代码变得简短了一些。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution
{
public:
    void connect(TreeLinkNode *root)
    {
        TreeLinkNode *h = new TreeLinkNode(0), *p = root;
        while(p != NULL)
        {
            h -> next = NULL;
            TreeLinkNode *cur = h;
            while(p != NULL)
            {
                if(p -> left != NULL)
                {
                    cur -> next = p -> left;
                    cur = cur -> next;
                }
                if(p -> right != NULL)
                {
                    cur -> next = p -> right;
                    cur = cur -> next;
                }
                p = p -> next;
            }
            p = h -> next;
        }
    }
};