leetcode_105. 从前序与中序遍历序列构造二叉树

举报
悲恋花丶无心之人 发表于 2021/02/03 01:01:38 2021/02/03
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:    ...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

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

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

例如,给出

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

    3
   / \
  9  20
    /  \
   15   7

二、解题思路

前序遍历:根->左->右,中序遍历:左->根->右,因此从前序遍历每次都取第一个元素进行构造,同时也找到取出的值在中序遍历里的位置,那么根据中序遍历的规则,该值的位置左边就是左子树元素右边就是右子树元素,递归构造即可。

三、代码


  
  1. # Definition for a binary tree node.
  2. class TreeNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.left = None
  6. self.right = None
  7. class Solution:
  8. def buildTree(self, preorder: list, inorder: list) -> TreeNode:
  9. def dfs(preorder, inorder):
  10. if inorder:
  11. val = preorder.pop(0)
  12. i = inorder.index(val)
  13. node = TreeNode(val)
  14. node.left = dfs(preorder, inorder[:i])
  15. node.right = dfs(preorder, inorder[i + 1:])
  16. return node
  17. return dfs(preorder, inorder)
  18. if __name__ == '__main__':
  19. preorder = [3,9,20,15,7]
  20. inorder = [9, 3, 15, 20, 7]
  21. s = Solution()
  22. ans = s.buildTree(preorder, inorder)
  23. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/108709801

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。