用时 :25min
主要思路是利用栈,和普通的层序遍历不同的是每次都把栈清空
1 | var connect = function(root) { |
很显然我使用的 On 的内存空间是不符合题目的常数空间的,考虑到每一层的链接可以依靠父节点,以链表的形式找到。如下代码
1 | while(pre) { |
剩下的需要考虑的有
pre需要保存为最左边的节点,以便于后面以链表的形式进行连接
第一层的next为空
最后一层没有左右节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18var 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
};