117. 填充每个节点的下一个右侧节点指针 II

此题为116. 填充每个节点的下一个右侧节点指针的进阶版本。

给定一个二叉树

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

1
2
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

提示：

  • 树中的节点数小于 6000
  • 100 <= node.val <= 100

Solution1（迭代版）：

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
35
class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        Node* head = root;
        Node* pre = NULL;
        while(root){
            Node* sub = NULL;
            while(pre){
                if(pre->left){
                    if(sub) sub->next = pre->left;
                    sub = pre->left;
                }
                if(pre->right){
                    if(sub) sub->next = pre->right;
                    sub = pre->right;
                }
                pre = pre->next;
            }
            pre = root;
            while(root){
                if(root->left){
                    root = root->left;
                    break;
                } else if(root->right){
                    root = root->right;
                    break;
                } else {
                    root = root->next;
                }
            }
        }
        return head;
    }
};

思路：

与上一题类似，先设置下父指针，找到父指针下所有存在的结点相连接，然后找到下一层的第一个结点，将其继续当做父节点。

Solution2（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    Node* connect(Node* root) {
        
        if(!root || (!root->left && !root->right)) return root;
        //先把当前结点连接
        if(root->left && root->right) root->left->next = root->right;
        Node* sub = root->right ? root->right : root->left;
        //跳过没有子节点的节点
        Node* head = root->next;
        while(head && !head->left && !head->right){
            head = head->next;
        }
        sub->next = head ? (head->left ? head->left : head->right) : NULL;
        connect(root->right);
        connect(root->left);
        return root;
    }
};

思路：

如果是叶子节点或空节点，则直接返回。
如果有两个子节点，先把两节点之间连接，把右节点当做下一层要操作的节点。
如果只有一个子节点，把该节点当做下一层要操作的节点。

将下一层的节点连接（寻找当前层的非叶子结点，将它的子节点与该结点的下一层节点连接）。

这里注意一定要先构建右子树，再构建左子树，因为寻找父节点的兄弟节点是从左到右遍历的，如果右子树未构建好就遍历，则会出错。