长大后想做什么？做回小孩！

0%

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

发表于 分类于 Valine：
本文字数： 685

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

JQPa7D.png

JQPU0O.png

思路一：层序遍历 和No.116姊妹题的分析一样，结果是用next将层序遍历节点连接。

实现和NO.116一样，但是借助队列完成层序遍历是不符合要求的，时间O(n)、空间也是O(n)。

思路二：借助next完成层序遍历 这里的分析和NO.116是一样的，主要来记录一下不同点。

连接都是分两种情况，但是NO.116是完美二叉树：父节点一定有左右孩子，所有左孩子连接右孩子，右孩子连接父节点next节点的左孩子。

但是本题没有限制为完美二叉树，所以需要额外增加很多判断去检查当前节点是否有左右孩子，尝试实现了一下，发现没有想象的简洁，没有很好的实现(方法是可行的)。

沿用NO.116的思路二进行改进实现，发现太过冗余并且复杂，所以换个思路实现：

因为我们还是需要层序遍历，但是不能借助队列，因为我们要降低空间复杂度，为什么思路一中不许要进行那么多冗杂的判空呢？因为我们在入队的时候进行了判空，确保入队的节点都是非空的。

不创建队列怎么记录一层的元素呢？用链表！每一层的元素用next指针连接起来就像是链表一样，我们用一个哑节点dummy指向每一层这个”链表”的开头、tail指向已经连接的”链表”的结尾，就像是入队一样逐个连接一层的元素。

如何遍历一层的元素？和NO.116一样，依然是用一个curr指向当前层的上一层，然后curr遍历上一层的父节点并判断每个父节点是否有左右孩子，如果有则在当前层进行连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Node connect(Node root) {
    Node curr = root;
    while (curr != null) {
        Node dummy = new Node();
        Node tail = dummy;
        //遍历当前层，判断每个节点是否有左右孩子
        while (curr != null) {
            if (curr.left != null) {
                tail.next = curr.left;
                tail = tail.next;
            }
            if (curr.right != null) {
                tail.next = curr.right;
                tail = tail.next;
            }
            //遍历当前层
            curr = curr.next;
        }
        //移动curr，遍历下一层
        curr = dummy.next;
    }
    return root;
}

时间复杂度：O(n)

空间复杂度：O(1) 只需要一个哑节点、一个尾指针

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github