从前序和中序遍历构造二叉树

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3

/ \

9 20

/ \

15 7

解析

考虑到前序遍历是：根-->左-->右，而中序遍历是：左-->根-->右。

所以可以用递归.首先看前序遍历第一位置,就是根节点,再看中序遍历,用这个根节点把中序遍历分成两部分.

# 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 not preorder:

return

id = inorder.index(preorder[0])

root = TreeNode(preorder[0])

root.left = self.buildTree(preoder[1:x+1],inorder[:x])

root.right = self.buildTree(preoder[x+1:],inorder[x+1:])

return root