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

用时 :25min

主要思路是利用栈,和普通的层序遍历不同的是每次都把栈清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var connect = function(root) {
if (!root) return null
var stack = [root]
while(stack.length) {
var _stack = [...stack,null]
stack = []
var pre = _stack.shift()
while(_stack.length || pre) {
pre.left && stack.push(pre.left)
pre.right && stack.push(pre.right)
pre.next = _stack.shift()
pre = pre.next
}
}
return root
};

很显然我使用的 On 的内存空间是不符合题目的常数空间的,考虑到每一层的链接可以依靠父节点,以链表的形式找到。如下代码

1
2
3
4
5
6
7
8
while(pre) {
var cur = pre
while(cur) {
cur.left.next = cur.right
cur.right.next = cur.next.left
cur = cur.next
}
}

剩下的需要考虑的有

  1. pre需要保存为最左边的节点,以便于后面以链表的形式进行连接

  2. 第一层的next为空

  3. 最后一层没有左右节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    var connect = function(root) {
    if(!root) return root
    var pre = root
    while(pre) {
    var cur = pre
    pre = pre.left
    while(cur) {
    if (cur.left) {
    cur.left.next = cur.right
    }
    if (cur.right && cur.next) {
    cur.right.next = cur.next.left
    }
    cur = cur.next
    }
    }
    return root
    };