题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
我的解法——递归（AC）
- 递归：
- 1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
- 2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点边和右边都为空，则根节点已经为叶子节点。
- 3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位
- 时间复杂度O(n)，空间复杂度O(n)
- Beat 57%
# 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 mybuildTree(self, preorder, inorder, l1, r1, l2, r2):
now = TreeNode(preorder[l1])
for index in range(l2, r2 + 1):
if(now.val == inorder[index]):
left_count = index - l2
right_count = r2 - index
if(left_count > 0):
now.left = self.mybuildTree(preorder, inorder, l1 + 1, l1 + left_count, l2, index - 1)
if(right_count > 0):
now.right = self.mybuildTree(preorder, inorder, l1 + left_count + 1, r1, index + 1, r2)
return now
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if(not len(preorder) or not len(inorder)):
return None
return self.mybuildTree(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)