LC-从前序与中序遍历序列构造二叉树

发表于 更新于 分类于

题目描述

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

代码实现

DFS（递归）

这是参考的评论区的一个解法，感觉十分易懂。这里的判断条件就是 l > r 是否成立。

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
/**
* 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) {
  function dfs(l, r) {
    if (l > r) {
      return null;
    }
    let val = preorder.shift();
    let root = new TreeNode(val);
    let index = inorder.indexOf(val);

    root.left = dfs(l, index - 1);
    root.right = dfs(index + 1, r);

    return root;
  }
  return dfs(0, inorder.length - 1)
}