leetcode_106. 从中序与后序遍历序列构造二叉树
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:
 ...
目录
一、题目内容
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树: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, inorder: list, postorder: list) -> TreeNode:
def dfs(inorder, postorder):
if inorder:
val = postorder.pop(-1)
i = inorder.index(val)
node = TreeNode(val)
node.right = dfs(inorder[i + 1:], postorder)
node.left = dfs(inorder[:i], postorder)
return node
return dfs(inorder, postorder)
if __name__ == '__main__':
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
s = Solution()
ans = s.buildTree(inorder, postorder)
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108710254
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)