专栏首页木又AI帮打卡群2刷题总结1011——从前序与中序遍历序列构造二叉树

打卡群2刷题总结1011——从前序与中序遍历序列构造二叉树


leetcode第105题:从前序与中序遍历序列构造二叉树

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]
返回如下的二叉树:
 3
   / \
  9  20
    /  \
   15   7

【思路】

首先回顾遍历的顺序:前序遍历是根节点-左子树-右子树,中序遍历是左子树-根节点-右子树。

那么前序遍历数组的第一个元素肯定是根节点,在中序遍历数组中找到这个元素,则其前一部分是左子树的元素,其后一部分是右子树的元素。递归即可求解。

注意:前序遍历+后序遍历,不能确定唯一的二叉树!

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # 前序遍历,第一个是head
        # 中序遍历,前一部分是左子树,后一部分是右子树
        if len(preorder) == 0:
            return None
        
        node = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        node.left = self.buildTree(preorder[1: index + 1], inorder[:index])
        node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return node

【相似题目】

106. 从中序与后序遍历序列构造二叉树

解题思路:后序遍历数组的最后一个元素是根节点的元素,同样在中序遍历数组中找到该元素,递归生成二叉树。

889. 根据前序和后序遍历构造二叉树

解题思路:直接生成只有右孩子的二叉树即可满足条件。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0810——从前序与中序遍历序列构造二叉树

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

    木又AI帮
  • 打卡群刷题总结0811——从中序与后序遍历序列构造二叉树

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

    木又AI帮
  • [Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

    根据二叉树的前序遍历和中序遍历( 中序和后序)结果生成二叉树 假设没有重复数字

    蛮三刀酱
  • 打卡群2刷题总结1009——二叉树的中序遍历

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    木又AI帮
  • 【LeetCode系列】从中序与后序遍历序列构造二叉树 & 从前序与中序遍历序列构造二叉树

    前序遍历是根左右,因此preorder第一个元素一定是整个树的根。由于题目说明了没有重复元素,因此我们可以通过preorder[0]去inorder找到根在in...

    深度学习技术前沿公众号博主
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮
  • 打卡群2刷题总结1010——二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    木又AI帮
  • ​LeetCode刷题实战105:从前序与中序遍历序列构造二叉树

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    程序IT圈
  • 105. 从前序与中序遍历序列构造二叉树

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

    祝你万事顺利
  • LC105-从前序与中序遍历序列构造二叉树

    可以将中序遍历得值合索引存在一个哈希表中,这样就可以找到根节点在中序遍历数组中的索引

    Java架构师必看
  • 打卡群刷题总结0808——二叉树的层序遍历

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 【Leetcode】105. 从前序与中序遍历序列构造二叉树

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

    Leetcode名企之路
  • LeetCode 105: 从前序与中序遍历序列构造二叉树

    Given preorder and inorder traversal of a tree, construct the binary tree.

    爱写bug
  • 力扣105——从前序与中序遍历序列构造二叉树

    原题url:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-i...

    健程之道
  • ​LeetCode刷题实战106:从中序与后序遍历序列构造二叉树

    https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde...

    程序IT圈
  • 106. 从中序与后序遍历序列构造二叉树

    CaesarChang张旭
  • 【Leetcode】106. 从中序与后序遍历序列构造二叉树

    中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

    Leetcode名企之路
  • LeetCode 0106. 从中序与后序遍历序列构造二叉树

    非常非常典型的题目,首先解决这道题我们需要明确给定一棵二叉树,我们是如何对其进行中序遍历与后序遍历的:

    Yano_nankai
  • LeetCode 106: 从中序与后序遍历序列构造二叉树

    Given inorder and postorder traversal of a tree, construct the binary tree.

    爱写bug

扫码关注云+社区

领取腾讯云代金券