当前位置:首页 > 编程笔记 > 正文
已解决

力扣:106. 从中序与后序遍历序列构造二叉树(Python3)

来自网友在路上 138838提问 提问时间:2023-09-22 21:23:29阅读次数: 38

最佳答案 问答题库388位专家为你答疑解惑

题目:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

示例:

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]


示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

解法:

使用栈辅助(stack),栈中每个结点结构为[当前结点在中序序列中的下标, 树节点],stack初始化的值是后序序列最后1个。

从后往前遍历后序序列, 从导数第2个开始。获取当前值在中序序列中的下标,如果比stack中最后1个大,说明当前结点是前个结点的右子树;否则需要弹出栈顶,直到比stack中最后1个小,此时说明当前结点是弹出结点的左子树。

知识点:

1.后序遍历:左-右-根。

代码:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:root = tree = TreeNode(postorder[-1])stack = [[inorder.index(postorder[-1]), tree]]for num in postorder[-2: -len(postorder) - 1: -1]:index = inorder.index(num)tree = TreeNode(num)if index > stack[-1][0]:stack[-1][1].right = treeelse:while stack and index < stack[-1][0]:pre = stack.pop()pre[1].left = treestack.append([index, tree])return root

查看全文

99%的人还看了

猜你感兴趣

版权申明

本文"力扣:106. 从中序与后序遍历序列构造二叉树(Python3)":http://eshow365.cn/6-11664-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!