ChunNote
0%

leetCode-117:Populating Next Right Pointers in Each Node II

发表于 分类于

问题描述

给定一个二叉树，要求填充每个节点的下一个节点（指向节点右边的兄弟节点，没有右边的节点则填充为空）。在不算递归栈的情况下，要求空间复杂度是常量。题目链接：**点我**

样例输入输出

输入：[1,2,3,4,5,null,7]

这是一个三层的二叉树，从上到下，从左到右的节点是：1，2，3，4，5，null，7。其中 1 的左孩子是 2，右孩子是 3，依次类推。其中 null 表示没有该节点，即 3 没有左孩子

输出：[1,#,2,3,#,4,5,7,#]

这是补充上节点右边节点后，按照从上到下，从左到右的节点的遍历的输出结果，其中 # 代表空

输入：[1]

输出：[1]

问题解法

此题跟 leetCode-116 类似，唯一的不同是，116 是一颗完全二叉树，而本次仅仅是一个二叉树，中间部分节点可能没有孩子。鉴于此，仍然可以用递归来解答，只不过需要改变一下递归的顺序，不能是 本节点 -> 左孩子 -> 右孩子 的顺序了，因为这样的顺序并不能保证在下一层中节点存在空缺时 next 指针的正确连接（因为本层的 next 指针没有完全连接好，所以不能顺着本层找到下层的节点）。需要改成 本节点 -> next 节点 -> 本节点的左孩子（没有左孩子就用右孩子），这样就能保证对当前节点的孩子进行 next 指针匹配时，当前节点右边的节点的 next 指针都已经匹配完成，从而能够为孩子节点的 next 指针匹配找到正确的节点。另外，需要注意的是，按照递归顺序，在 next 递归中，会存在对节点重复遍历的情况，此时进行剪枝判断，如果 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution
{
    public Node connect(Node root)
    {
        // root.left != null && root.left.next != null 是剪枝判断，避免重复遍历
        // root.right != null && root.right.next != null 是剪枝判断，避免重复遍历
        if (root == null || (root.left != null && root.left.next != null) || (root.right != null && root.right.next != null))
        {
            return root;
        }
        
        Node from;    // 当前节点的某个孩子节点，需要指向 父节点的兄弟节点的孩子
        Node first;   // 当前节点的某个孩子节点，下一层遍历开始的节点
        if (root.left != null)
        {
            first = root.left;
            if (root.right != null)
            {
                root.left.next = root.right;
                from = root.right;
            }
            else
            {
                from = root.left;
            }
        }
        else
        {
            first = root.right;
            from = root.right;
        }
        
        if (from != null)
        {
            Node to = null;
            Node temp = root.next;
            while (temp != null)
            {
                if (temp.left != null)
                {
                    to = temp.left;
                    break;
                }
                
                if (temp.right != null)
                {
                    to = temp.right;
                    break;
                }
                
                temp = temp.next;
            }
            
            from.next = to;
        }

        connect(root.next);
        connect(first);
        
        return root;
    }
}