105-从前序与中序遍历序列构造二叉树

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
606
文章
12
评论
2020年2月7日23:31:14 评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

例如,给出前序遍历 preorder = [3,9,20,15,7],中序遍历 inorder = [9,3,15,20,7],返回如下的二叉树:

二、题解

这道题在《剑指offer》也出现了,题目完全一样。主要用到了树的两个特性:

  • 前序遍历的首元素为根节点。
  • 中序遍历中,根节点的左边是左子树,根节点的右边是右子树。

解题的思路就是:通过前序遍历得到根节点,然后在中序遍历中找到这个节点,再通过递归的方式找出左右子树。

详细的分析可以参考《剑指offer》面试题7:重建二叉树

三、代码:

执行通过:

105-从前序与中序遍历序列构造二叉树

马谦马谦马谦
  • 本文由 发表于 2020年2月7日23:31:14
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/construct-binary-tree-from-preorder-and-inorder-traversal.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: