【LeetCode 二叉树专项】从中序与后序遍历序列构造二叉树(106)
1. 题目
定一棵树的中序遍历 inorder
与后序遍历 postorder
序列。请构造二叉树并返回其根节点。
1.1 示例
-
示例
1
1
- 输入:
inorder = [9, 3, 15, 20, 7]
,postorder = [9, 15, 7, 20, 3]
- 输出:
[3, 9, 20, null, null, 15, 7]
- 示例
2
2
- 输入:
inorder = [-1]
,postorder = [-1]
- 输出:
[-1]
1.2 说明
1.3 限制
-
1 <= preorder.length <= 3000
; -
postorder.length == inorder.length
; -
-3000 <= inorder[i], postorder[i] <= 3000
; -
inorder
和postorder
均无重复元素; -
inorder
均出现在postorder
; -
inorder
保证为二叉树的中序遍历序列; -
postorder
保证为二叉树的后序遍历序列。
2. 解法一(递归)
2.1 分析
此题和【LeetCode 二叉树专项】从前序与中序遍历序列构造二叉树(105)十分类似,解答的方法也相近。下面仅给出三张示意图:
- 如何通过
postorder
序列找到根节点对应val
域及其在inorder
序列中的索引; - 如何通过根节点在
inorder
序列中的索引递归构建根节点的左子节点; - 如何通过根节点在
inorder
序列中的索引递归构建根节点的右子节点。
2.2 实现
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def _build_tree(self, inorder: List[int], in_start: int, in_stop: int,
postorder: List[int], post_start: int, post_stop) -> Optional[TreeNode]:
if in_start > in_stop or post_start > post_stop:
return
index = inorder.index(postorder[post_stop])
root = TreeNode(postorder[post_stop])
root.left = self._build_tree(inorder, in_start, index - 1,
postorder, post_start, post_start + index - 1 - in_start)
root.right = self._build_tree(inorder, index + 1, in_stop,
postorder, post_stop - in_stop + index, post_stop - 1)
return root
def build_tree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
return self._build_tree(inorder, 0, len(inorder) - 1, postorder, 0, len(inorder) - 1)
def main():
inorder = [5, 2, 6, 4, 7, 1, 8, 3, 9]
postorder = [5, 6, 7, 4, 2, 8, 9, 3, 1]
sln = Solution()
root = sln.build_tree(inorder, postorder)
tree = []
visiting = deque([root])
while visiting:
node = visiting.popleft()
if node:
tree.append(node.val)
visiting.append(node.left)
visiting.append(node.right)
else:
tree.append(None)
while True:
if not tree[-1]:
tree.pop()
else:
break
print(tree) # [1, 2, 3, 5, 4, 8, 9, None, None, 6, 7]
if __name__ == '__main__':
main()
2.3 复杂度
-
时间复杂度:
O
(
n
)
O(n)
n
n
-
空间复杂度:
O
(
n
)
O(n)
O
(
n
)
O(n)
O
(
h
)
O(h)
h
h
h
<
n
h < n
O
(
n
)
O(n)
3. 解法二(迭代)
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码