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

发表于 | 分类于
思路是BFS，稍微有一点改变

用时 ：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
    };