Voyz's Studio.

LeetCode算法笔记--从前序与中序遍历序列构造二叉树

字数统计: 284阅读时长: 1 min
2020/12/28 Share

LeetCode算法笔记-Day53

105. 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.

example:

1
2
3
4
5
6
7
8
9
10
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

3
/ \
9 20
/ \
15 7

Analyse:

  • 变量 pre 保存当前要构造的树的 root
  • 变量 in 保存 inorder 数组中可以成为 root 的数字们的开头那个
  • 对于当前要构造的树,有一个停止点 stop ,inorder 数组中第 in 项到第 stop 项是要构造的树的节点值们
  • 每次递归调用,都会确定出一个停止点,它告诉了子调用在哪里停止,把自己的根节点值作为左子树调用的停止点,自己的(父调用给下来的)停止点作为右子树的停止点  

Answer:

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/

var buildTree = function(preorder, inorder) {
pre = i = 0
build = function(stop) {
if (inorder[i] != stop) {
var root = new TreeNode(preorder[pre++])
root.left = build(root.val)
i++
root.right = build(stop)
return root
}
return null
}
return build()
};
CATALOG
  1. 1. LeetCode算法笔记-Day53
    1. 1.1. 105. Construct Binary Tree from Preorder and Inorder Traversal
    2. 1.2. Analyse:
      1. 1.2.1. Answer: