-
Notifications
You must be signed in to change notification settings - Fork 1
/
interviewbit-453-burnATree.js
168 lines (141 loc) · 4.01 KB
/
interviewbit-453-burnATree.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
// Definition for a binary tree node
// function TreeNode(data){
// this.data = data
// this.left = null
// this.right = null
// }
const burn = (A, B) => {
return _findB(A, B) + _findO(A, B) - 1;
};
// Tree : 12
// / \
// 21 3i
// / / \
// 40 5i 6i
// \
// 7i
// Tree : 14
// / \
// 2-i 33
// / / \
// 4-i 51 62
// \
// 71
// \
// 8
// \
// 9
// / \
// 10 11
// dfs recusrive O(n) O(n)
const _findB = (root, leaf) => {
if (!root) return Infinity;
if (root.val === leaf) return 0;
const left = _findB(root.left, leaf);
const right = _findB(root.right, leaf);
return 1 + Math.min(left, right);
};
const _findO = (root, leaf) => {
if (!root) return 0;
if (root.val === leaf) return -Infinity;
const left = _findO(root.left, leaf);
const right = _findO(root.right, leaf);
return 1 + Math.max(left, right);
};
// const burn = function (root, B) {
// // Initialize the minimum burning time and current burning time to zero
// let min_time = 0;
// let cur_time = 1;
// // Helper function to perform DFS and find the minimum time required
// // to burn the entire tree
// function dfs(node) {
// // If the current node is the leaf node that we are looking for,
// // return the current burning time
// if (node.val == B) {
// min_time = cur_time;
// return;
// }
// // If the current node has a left child, recursively call the
// // DFS function on the left child and increment the current
// // burning time by one
// if (node.left) {
// cur_time += 1;
// dfs(node.left);
// }
// // If the current node has a right child, recursively call the
// // DFS function on the right child and increment the current
// // burning time by one
// if (node.right) {
// cur_time += 1;
// dfs(node.right);
// }
// }
// // Start the DFS from the root node
// dfs(root);
// // Return the minimum time required to burn the entire tree
// return min_time;
// };
// const burn = function (root, B) {
// // Initialize the minimum burning time and current burning time to zero
// let min_time = 0;
// let cur_time = 1;
// // Create a stack to store the nodes for the iterative DFS
// const stack = [];
// // Push the root node to the stack
// stack.push(root);
// // Continue the iterative DFS while the stack is not empty
// while (stack.length > 0) {
// // Pop the top node from the stack
// const node = stack.pop();
// // If the current node is the leaf node that we are looking for,
// // update the minimum burning time and break out of the loop
// if (node.val == B) {
// min_time = cur_time;
// break;
// }
// // If the current node has a right child, push it to the stack
// // and increment the current burning time by one
// if (node.right) {
// stack.push(node.right);
// cur_time += 1;
// }
// // If the current node has a left child, push it to the stack
// // and increment the current burning time by one
// if (node.left) {
// stack.push(node.left);
// cur_time += 1;
// }
// }
// // Return the minimum time required to burn the entire tree
// return min_time;
// };
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
const a = new Node(1);
const b = new Node(2);
const c = new Node(3);
const d = new Node(4);
const e = new Node(5);
const f = new Node(6);
const g = new Node(7);
const h = new Node(8);
const i = new Node(9);
const j = new Node(10);
const k = new Node(11);
a.left = b;
a.right = c;
b.left = d;
c.left = e;
c.right = f;
f.right = g;
g.right = h;
h.right = i;
i.left = j;
i.right = k;
// console.log(a.right);
console.log(burn(a, 4));