题眼
这个题目就是典型的递归题目.
这里就是根据前序和后续的二叉树的具体结构特征来做.
python 的 slice让这个题目的coding难度降低了很多.
解题过程
- 取前序数列的第一个数作为
root - 根据
root.val将中序序列划分为两个部分,left_in和left_right - 根据
len(left_in)将前序序列划分为两个部分left_pre和left_right - 递归构建左子树和右子树
需要注意的地方
注意序列的长度在划分之后, 会变成0
代码质量
这里可以使用guard clause手法或者说是fast return将代码的嵌套减少.
代码详解
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# guard clause
# fast return
if len(preorder)==0:
return None
# 这里确定 preorder 的长度>0
root = TreeNode(preorder.pop(0))
# 扁平状的序列可能为空
left_in = inorder[:inorder.index(root.val)]
# 扁平状的序列可能为空
right_in = inorder[inorder.index(root.val)+1:]
# left_in 可能为空
if len(left_in)>0:
left_pre = preorder[:len(left_in)]
root.left = self.buildTree(left_pre, left_in)
# right_in 可能为空, 比如链表状二叉树
if len(right_in)>0:
right_pre = preorder[len(left_in):]
root.right = self.buildTree(right_pre, right_in)
return root
