原題
根據(jù)前序遍歷和中序遍歷樹構(gòu)造二叉樹.
給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹:
2
/ \
1 3
你可以假設(shè)樹中不存在相同數(shù)值的節(jié)點(diǎn)
解題思路
- 本題與通過中序和后序遍歷構(gòu)造二叉樹類似苹丸，同樣是遞歸解決
- 前序遍歷數(shù)組的第一個值為根節(jié)點(diǎn)，根據(jù)這個值可以將中序遍歷數(shù)組分成左右兩部分，分別為左子樹和右子樹
完整代碼
# 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
"""
if inorder:
index = inorder.index(preorder[0])
del preorder[0]
root = TreeNode(inorder[index])
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index + 1:])
return root
