leetcode-106 从中序与后序遍历序列构造二叉树

  • English:

leetcode-106 从中序与后序遍历序列构造二叉树

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

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

例如,给出

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

思路:

和之前题目的思路类似,通过后续遍历的最后一个元素可以确定根节点,通过后序遍历的根节点找到中序遍历中根节点的位置,确定左右子树,递归处理即刻。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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[int], postorder: List[int]) -> TreeNode:
root = self.build(inorder, 0, len(inorder)-1, postorder, 0, len(postorder)-1)
return root
sz
def build(self, inorder, instart, inend, postorder, poststart, postend):
if poststart > postend:
return
rootVal = postorder[postend]
index = 0
for i in range(instart, inend+1):
if inorder[i] == rootVal:
index = i
break
root = TreeNode(rootVal)
leftsize = index - instart
root.left = self.build(inorder, instart, index-1, postorder, poststart, poststart+leftsize-1)
root.right = self.build(inorder, index + 1, inend, postorder, poststart+leftsize, postend-1)
return root
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/24682/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!