原題

根據(jù)前序遍歷和中序遍歷樹(shù)構(gòu)造二叉樹(shù).

給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹(shù):

  2
 / \
1   3

你可以假設(shè)樹(shù)中不存在相同數(shù)值的節(jié)點(diǎn)

解題思路

• 本題與通過(guò)中序和后序遍歷構(gòu)造二叉樹(shù)類似，同樣是遞歸解決
• 前序遍歷數(shù)組的第一個(gè)值為根節(jié)點(diǎn)，根據(jù)這個(gè)值可以將中序遍歷數(shù)組分成左右兩部分，分別為左子樹(shù)和右子樹(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