LEETCODE 105. 从前序与中序遍历序列构造二叉树
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 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 """ def recursion(pre_order, in_order): if(not pre_order or not in_order): return None if(len(pre_order)==1 and len(in_order)==1): return TreeNode(pre_order[0]) root = TreeNode(pre_order[0]) index = in_order.index(pre_order[0]) in_left = in_order[:index] in_right = in_order[index+1:] index = len(in_left)+1 pre_left = pre_order[1:index] pre_right = pre_order[index:] root.left = recursion(pre_left, in_left) root.right = recursion(pre_right, in_right) return root return recursion(preorder, inorder)2 次阅读