Repository navigation
Expand file tree
/
Copy pathNo116.populating-next-right-pointers-in-each-node.js
More file actions
102 lines (96 loc) · 2.65 KB
/
Copy pathNo116.populating-next-right-pointers-in-each-node.js
File metadata and controls
102 lines (96 loc) · 2.65 KB
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
* Difficulty:
* Medium
*
* Desc:
* Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
* Populate each next pointer to point to its next right node.
* If there is no next right node, the next pointer should be set to NULL.
* Initially, all next pointers are set to NULL.
*
* Note:
* You may only use constant extra space.
* You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
*
* Example:
* Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
* After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
*
* 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。
* 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
* 初始状态下,所有 next 指针都被设置为 NULL。
*
* 你只能使用常量级额外空间。
* 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
*/
/**
* Definition for binary tree with next pointer.
* function TreeLinkNode(val) {
* this.val = val;
* this.left = this.right = this.next = null;
* }
*/
/**
* @param {TreeLinkNode} root
* @return {void} Do not return anything, modify tree in-place instead.
*/
var connect_1 = function(root) {
const connectRight = (nodes) => {
const nextNodes = [];
let pre = null;
while (nodes.length) {
const node = nodes.shift();
if (!node) break;
if (pre) pre.next = node;
pre = node;
if (pre.left) nextNodes.push(pre.left, pre.right);
}
if (nextNodes.length) connectRight(nextNodes);
};
connectRight([root]);
};
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var connect_2 = function(root) {
if (!root) return null
const queue = [root]
while (queue.length) {
let len = queue.length
let pre = null
while (len) {
const node = queue.shift()
if (pre) pre.next = node
pre = node
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
len -= 1
}
}
return root
}