Leetcode(117) Populating Next Right Pointers in Each Node II

发表于 | 分类于

Description

Given a binary tree

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

img

Note:

  • You may only use constant extra space.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.

解法

116题的改版，只需要在连接前遍历父节点层找到下一个邻接节点即可，注意递归的时候应该先递归右边的部分，确保右边的next已经完全连上了，否则会导致结果的错误（在这个坑里WA了半天才想明白）。

具体代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        if(root.left != null){
            if(root.right != null){
                root.left.next = root.right;
            }
            else{
                Node tmp = root;
                while(tmp.next != null){
                    if(tmp.next.left != null){
                        root.left.next = tmp.next.left;
                        break;
                    }
                    else if(tmp.next.right != null){
                        root.left.next = tmp.next.right;
                        break;
                    }
                    else{
                        tmp = tmp.next;
                    }
                }
            }
        }
        if(root.right != null){
            Node tmp = root;
            while(tmp.next != null){
                if(tmp.next.left != null){
                    root.right.next = tmp.next.left;
                    break;
                }
                else if(tmp.next.right != null){
                    root.right.next = tmp.next.right;
                    break;
                }
                else{
                    tmp = tmp.next;
                }
            }
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
}