【題目】

根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
 3
   / \
  9  20
    /  \
   15   7

【思路】

首先回顧遍歷的順序：前序遍歷是根節點-左子樹-右子樹，中序遍歷是左子樹-根節點-右子樹。

那么前序遍歷數組的第一個元素肯定是根節點，在中序遍歷數組中找到這個元素，則其前一部分是左子樹的元素，其后一部分是右子樹的元素。遞歸即可求解。

注意：前序遍歷+后序遍歷，不能確定唯一的二叉樹！

【代碼】

python版本

# 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
        """
        # 前序遍歷，第一個是head
        # 中序遍歷，前一部分是左子樹，后一部分是右子樹
        if len(preorder) == 0:
            return None
        
        node = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        node.left = self.buildTree(preorder[1: index + 1], inorder[:index])
        node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return node

【相似題目】

從中序與后序遍歷序列構造二叉樹

解題思路：后序遍歷數組的最后一個元素是根節點的元素，同樣在中序遍歷數組中找到該元素，遞歸生成二叉樹。

根據前序和后序遍歷構造二叉樹

解題思路：直接生成只有右孩子的二叉樹即可滿足條件。