塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-7重建二叉树-python

《剑指offer》python实现系列,全目录

先根据先序遍历的第一位确定根节点,
确定根节点后,中序遍历中根节点左边的是左子树,右边的是右子树。

对于左子树重复此操作,根据左子树的先序遍历的第一个元素为左子树的根节点,再看中序遍历。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
def reConstructBinaryTree(self, pre, tin):
#pre表示前序遍历的序列,tin表示中序遍历的序列
if not pre or not tin:
return None
root = TreeNode(pre[0]) #前序遍历的第一个表示root结点
rootIndex = tin.index(pre[0])#root在中序遍历序列中的索引

#根据中序遍历,处理左子树,切片表示在前序和中序中的左子树
root.left = self.reConstructBinaryTree(pre[1:rootIndex+1], tin[0:rootIndex])
#根据中序遍历,处理右子树,切片表示在前序和中序中的右子树
root.right= self.reConstructBinaryTree(pre[rootIndex+1:], tin[rootIndex+1:])

return root

注意
a=[1,2,3]
print(a[4:4])
out:[]

if help:小手一抖点个广告 or 大手一挥资助一下