leetcode-105 从前序与中序遍历序列构造二叉树

  • English:

leetcode-105 从前序与中序遍历序列构造二叉树

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

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

例如,给出

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

返回如下的二叉树:

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
27
28
# 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[int], inorder: List[int]) -> TreeNode:
root = self.build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
return root


def build(self, preorder, prestart, preend, inorder, instart, inend):
if prestart > preend:
return
rootval = preorder[prestart]
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(preorder,prestart+1, prestart+leftsize ,inorder, instart, index-1)
root.right = self.build(preorder,prestart+leftsize+1,preend ,inorder, index+1, inend)

return root
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/64977/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!