剑指offer - 重建二叉树 - JavaScript

题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

# 题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

# 解法 1: 递归

首先前序/后序遍历 + 中序遍历可以重建二叉树。题目考察的就是前序+中序来重建二叉树,后序+中序的思路是类似的。

# 例子与思路

假设有二叉树如下:

    1
   / \
  2   3
 / \
4   5

它的前序遍历的顺序是:1 2 4 5 3。中序遍历的顺序是:4 2 5 1 3

因为前序遍历的第一个元素就是当前二叉树的根节点。那么,这个值就可以将中序遍历分成 2 个部分。在以上面的例子,中序遍历就被分成了 4 2 53 两个部分。4 2 5就是左子树,3就是右子树。

最后,根据左右子树,继续递归即可。

专注前端与算法的系列干货分享,欢迎关注(¬‿¬):
「微信公众号:心谭博客」| xxoo521.com | GitHub

# 代码实现

// ac地址:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
// 原文地址:https://xxoo521.com/2019-12-21-re-construct-btree/

/**
 * 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 || !inorder.length) {
    return null;
  }

  const rootVal = preorder[0];
  const node = new TreeNode(rootVal);

  let i = 0; // i有两个含义,一个是根节点在中序遍历结果中的下标,另一个是当前左子树的节点个数
  for (; i < inorder.length; ++i) {
    if (inorder[i] === rootVal) {
      break;
    }
  }

  node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
  node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
  return node;
};