[路飞]_leetcode-105-从前序与中序遍历序列构造二叉树

简介: leetcode-105-从前序与中序遍历序列构造二叉树

网络异常,图片无法展示
|


[题目地址][B站地址]


给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。


示例 1:


网络异常,图片无法展示
|


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
复制代码


示例 2:


Input: preorder = [-1], inorder = [-1]
Output: [-1]
复制代码


提示:


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


本题解题思路如下:


  1. 前序遍历的顺序为根左右,中序遍历的顺序为左根右,所以 preorder[0] 为当前子树根节点的值
  2. 查找该值在 inorder 中的位置,其左边即为左子树中序遍历序列,右边为右子树中序遍历序列
  3. 获取到左右子树中序遍历后,因为子树前序遍历和中序遍历的结果只是顺序不同,但是序列长度是相同的,所以可以根据左子树中序遍历序列长度去 preorder 获取左子树前序遍历序列,剩余部分即为右子树前序遍历序列
  4. 然后就可以通过根节点的值创建根节点,根据左右子树的前序、中序遍历序列递归创建左右子树
  5. 最后返回二叉树的根节点即可


动画演示如下:

网络异常,图片无法展示
|

第一版代码如下:


var buildTree = function(preorder, inorder) {
  // 如果前序遍历序列为空,返回空
  if(preorder.length === 0) return null;
  // 创建子树根节点
  const root = new TreeNode(preorder.shift()),
  // 获取根节点值在中序遍历序列的下标
  ind = inorder.indexOf(root.val);
  // 通过根节点值在中序遍历序列的下标,截取左子树前序遍历,中序遍历序列,创建左子树
  root.left = buildTree(preorder.splice(0,ind),inorder.splice(0,ind));
  // 根据剩余部分截取右子树前序遍历,中序遍历序列,创建右子树
  root.right = buildTree(preorder,inorder.splice(1));
  // 返回根节点
  return root;
};
复制代码


这一版代码提交通过后,只击败了 50% 左右的用户,是因为在递归过过程需要截取左右子树的前序、中序遍历序列,这样的操作增加了执行用时和空间复杂度。


这里我们可以通过维护当前子树前序遍历序列开始结束下标,及中序遍历序列开始结束下标代替截取前序、中序遍历序列的操作,同样达到递归构建左右子树的目的。


优化后代码如下:


var buildTree = function(preorder, inorder) {
  // 传入前序遍历序列开始下标,结束下标,中序遍历序列开始下标
  function build(preStart,preEnd,inStart){
    // 如果前序遍历序列开始下标大于结束下标,说明区间处理完成,返回 null
    if(preStart>preEnd) return null;
    // 通过前序遍历开始下标值构建根节点
    const root = new TreeNode(preorder[preStart]),
    // 获取根节点值在中序遍历序列的下标
    ind = inorder.indexOf(root.val),
    // 获取中序遍历左子树的长度
    leftSize = ind-inStart;
    // 递归的构建左右子树
    root.left = build(preStart+1,preStart+leftSize,inStart);
    root.right = build(preStart+leftSize+1,preEnd,ind+1);
    return root;
  }
  // 返回构建后二叉树的根节点
  return build(0,preorder.length-1,0)
};
复制代码


至此我们就完成了 leetcode-105-从前序与中序遍历序列构造二叉树


如有任何问题或建议,欢迎留言讨论!

相关文章
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
7天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
28天前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
28天前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
28天前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
1月前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
1月前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
|
14天前
|
存储 算法
力扣经典150题第四十六题:最长连续序列
力扣经典150题第四十六题:最长连续序列
5 0
|
1月前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度