06. 重建二叉树

来源

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

题目

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

示例:

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

思路

前序遍历第一个元素 3 就是根节点，在中序遍历里根节点左侧的是左子树节点，右侧的是右子树节点，在前序遍历里 9 就是左子树，20、15、7 是右子树，同理可以推出 20 为右子树的根节点，15 在左侧，7 在右侧。

解题

/**
 * 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) {
  if (preorder.length === 0) return null;

  const root = preorder[0];
  const rootIndex = inorder.indexOf(root); // 1
  const inorderLeft = inorder.slice(0, rootIndex); // 左子树中序
  const inorderRight = inorder.slice(rootIndex + 1); // 右子树中序
  const preorderLeft = preorder.slice(1, 1 + rootIndex); // 左子树前序
  const preorderRight = preorder.slice(1 + rootIndex); // 右子树前序
  const rootNode = new TreeNode(root);
  rootNode.left = buildTree(preorderLeft, inorderLeft);
  rootNode.right = buildTree(preorderRight, inorderRight);

  return rootNode;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch