leetcode_105. 从前序与中序遍历序列构造二叉树
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如,给出
前序遍历 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
二、解题思路
前序遍历:根->左->右,中序遍历:左->根->右,因此从前序遍历每次都取第一个元素进行构造,同时也找到取出的值在中序遍历里的位置,那么根据中序遍历的规则,该值的位置左边就是左子树元素,右边就是右子树元素,递归构造即可。
三、代码
-
# Definition for a binary tree node.
-
class TreeNode:
-
def __init__(self, x):
-
self.val = x
-
self.left = None
-
self.right = None
-
-
class Solution:
-
def buildTree(self, preorder: list, inorder: list) -> TreeNode:
-
def dfs(preorder, inorder):
-
if inorder:
-
val = preorder.pop(0)
-
i = inorder.index(val)
-
node = TreeNode(val)
-
node.left = dfs(preorder, inorder[:i])
-
node.right = dfs(preorder, inorder[i + 1:])
-
return node
-
return dfs(preorder, inorder)
-
-
-
if __name__ == '__main__':
-
preorder = [3,9,20,15,7]
-
inorder = [9, 3, 15, 20, 7]
-
-
s = Solution()
-
ans = s.buildTree(preorder, inorder)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108709801
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)