题目描述

原题链接

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
image.png
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

个人解法

Javascript

  1. /*
  2.  * @lc app=leetcode.cn id=105 lang=javascript
  3.  *
  4.  * [105] 从前序与中序遍历序列构造二叉树
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for a binary tree node.
  10.  * function TreeNode(val, left, right) {
  11.  *     this.val = (val===undefined ? 0 : val)
  12.  *     this.left = (left===undefined ? null : left)
  13.  *     this.right = (right===undefined ? null : right)
  14.  * }
  15.  */
  16. // const fun = function (preorder, inorder) {
  18. // }
  19. /**
  20.  * @param {number[]} preorder
  21.  * @param {number[]} inorder
  22.  * @return {TreeNode}
  23.  */
  24. var buildTree = function (preorder, inorder) {
  25.   if (preorder.length === 0) {
  26.     return null;
  27.   }
  28.   const root = new TreeNode(preorder[0]);
  29.   const index = inorder.indexOf(preorder[0]);
  30.   root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
  31.   root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
  32.   return root;
  33. };
  34. // @lc code=end

Java

其他解法

Java

Javascript

由于 多次数组的截取 和 indexOf 很耗费时间，所以要对代码进行下优化
优化代码

  1. const buildTree = (preorder, inorder) => {
  2.   const map = new Map();
  3.   for (let i = 0; i < inorder.length; i++) {
  4.     map.set(inorder[i], i);
  5.   }
  6.   const helper = (p_start, p_end, i_start, i_end) => {
  7.     if (p_start > p_end) return null;
  8.     let rootVal = preorder[p_start];    // 根节点的值
  9.     let root = new TreeNode(rootVal);   // 根节点
  10.     let mid = map.get(rootVal);         // 根节点在inorder的位置
  11.     let leftNum = mid - i_start;        // 左子树的节点数
  12.     root.left = helper(p_start + 1, p_start + leftNum, i_start, mid - 1);
  13.     root.right = helper(p_start + leftNum + 1, p_end, mid + 1, i_end);
  14.     return root;
  15.   };
  16.   return helper(0, preorder.length - 1, 0, inorder.length - 1);
  17. };

方法二：迭代

题解链接