-
Notifications
You must be signed in to change notification settings - Fork 1
/
114-Flatten Binary Tree to Linked List.js
105 lines (99 loc) · 2.53 KB
/
114-Flatten Binary Tree to Linked List.js
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
103
104
105
/**
* Problem link: https://leetcode.com/problems/flatten-binary-tree-to-linked-list
* 114: Flatten Binary Tree to Linked List
*
* Input: root = [1,2,5,3,4,null,6]
* Output: [1,null,2,null,3,null,4,null,5,null,6]
*
* Input: root = []
* Output: []
*
* Input: root = [0]
* Output: [0]
*
* Solution: Binary Tree, DFS, Morris Algorithm, Stack, Linked List, Tree
*/
/**
* Runtime: 95 ms
* Memory Usage: 45.1 MB
*/
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.val = value;
}
}
/**
* Solution 1: Traverse from bottom i.e. shift one by one into linked list from bottom
* head.shift(6): 6
* head.shift(5) : 5 6
* head.shift(4) : 4 5 6
* ...
* 1 2 3 4 5 6
*
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
let head = null, curr = root
while (head != root) {
if (curr.right === head) {
curr.right = null;
}
if (curr.left === head) {
curr.left = null;
}
if (curr.right) {
curr = curr.right;
}
else if (curr.left) {
curr = curr.left;
}
else {
curr.right = head; head = curr;
curr = root;
}
}
};
/**
* Solution 2: Morris traversal
* Insertion process:
* 4 -> R [ 5 6 ] ---> 2 ->[L 3, R [4 R [5 6]]]
* 3 -> R [4 R [5 6]] --> 2 ->[Null, [3 -> L , R [[4 R [5 6]]]]
* @param root
*/
var morrisTraversal = function (root) {
// TODO: this is wrong, need more study
let next = root;
const result = [];
while (next) {
if (next.left) {
let current = next.left;
while (current.right && current.right != next) {
current = current.right;
}
if (current.right == next)
{
current.right = null;
next = next.right;
} else {
result.push(next.val)
current.right = next;
next = next.left;
}
} else {
result.push(next.val)
next = next.right;
}
}
return result;
}
root = new Node(1);
root.left = new Node(2);
root.right = new Node(5);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.right = new Node(6);
console.log("result 1: ", morrisTraversal (root));
// console.log("result 1: ", flatten (root));