剑指 Offer 07. 重建二叉树
文章目录

题目

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

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

返回如下的二叉树:

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

限制:

1
0 <= 节点个数 <= 5000

链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

题解

二叉树建树系列问题的解答和树的遍历方式有很大的关系。

不同的遍历方式将会有不同的解答。

解答逻辑:

  1. 以前序遍历的数组为基准, 每次从前序遍历取出数组头部第一个元素 x.
  2. 对当前的中序遍历数组根据 x 进行切割, x 左边的元素肯定就在 x 的左子树, x 右边的元素就一定在 x 的右子树.
  3. 继续从前序遍历数组取出第二个元素, 并且对刚才切割出来的左右子树进行再次切割
    • 如果无法切割说明全部放到左子树
    • 如果切割后只有一个元素说明直接就是叶子节点了
  4. 递归执行切割操作直到前序遍历的数组全部用完为止
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[]} preorderv
* @param {number[]} inorder
* @return {TreeNode}
*/

var buildTree = function (preorder, inorder) {
if (!inorder || inorder.length === 0) return null
let i;
for (i = 0; i < preorder.length; i++) {
if (inorder.includes(preorder[i])) break;
}
const n = preorder[i];
const left = inorder.slice(0, inorder.indexOf(n))
const right = inorder.slice(inorder.indexOf(n) + 1, inorder.length);

const head = new TreeNode(n)
head.left = buildTree(preorder.slice(1, preorder.length), left)
head.right = buildTree(preorder.slice(1, preorder.length), right)
return head;
};