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

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

题目：
大体和题目116相同，只是给定的二叉树并不受限制

思路：
递归法

  • 如果一个节点root既有左子节点又有右子节点，则左子节点的next指向右子节点，右子节点的next指向NextNoNullChild
  • 如果一个节点只有左子节点，则左子节点的next指向其NextNoNullChild
  • 如果一个节点只有右子节点，则右子节点的next指向其NextNoNullChild

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

BFS广度优先搜索：
116题的BFS解答同样适用于该题

代码： 

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
class Solution {
    public Node connect(Node root) {
        if(root == null)
            return null;
        if(root.right == null && root.left == null)
            return root;
        if(root.right != null && root.left != null){
            root.left.next = root.right;
            root.right.next = NextNoNullChild(root);
        }
        if(root.right == null)
            root.left.next = NextNoNullChild(root);
        if(root.left == null)
            root.right.next = NextNoNullChild(root);

        root.right = connect(root.right);
        root.left = connect(root.left);
        return root;
    }
    //用while循环，找到和root及其兄弟节点的的下一个不为null的子节点
    public Node NextNoNullChild(Node root){
        if(root == null)
            return null;
        while(root.next != null){
            if(root.next.left != null)
                return root.next.left;
            if(root.next.right != null)
                return root.next.right;
            root = root.next;
        }
        return null;
    }
}