-
Notifications
You must be signed in to change notification settings - Fork 86
/
Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.js
83 lines (70 loc) · 1.6 KB
/
Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.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
/*
Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
var TreeNode = require("../../../UtilsClasses/TreeNode").TreeNode;
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
if (
preorder === null ||
inorder === null ||
preorder.length !== inorder.length
)
return null;
return buildTreeAux(
preorder,
0,
preorder.length - 1,
inorder,
0,
inorder.length - 1
);
};
var buildTreeAux = function (preorder, pl, ph, inorder, il, ih) {
if (pl > ph || il > ih) return null;
const rootValue = preorder[pl];
var countElementsLeft = 0;
while (inorder[il + countElementsLeft] !== rootValue) countElementsLeft++;
var ret = new TreeNode(rootValue);
ret.left = buildTreeAux(
preorder,
pl + 1,
pl + countElementsLeft,
inorder,
il,
il + countElementsLeft - 1
);
ret.right = buildTreeAux(
preorder,
pl + countElementsLeft + 1,
ph,
inorder,
il + countElementsLeft + 1,
ih
);
return ret;
};
module.exports.buildTree = buildTree;