根据前序和中序遍历构建二叉树
DescriptionExample题意解题思路code
105. Construct Binary Tree from Preorder and Inorder Traversal Medium
Description
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
Example
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
题意
根据前序和中序遍历构建二叉树
解题思路
学过数据结构的应该都知道，前序和中序遍历可以唯一确定一颗二叉树。首先前序遍历的首元素肯定是根结点，那么在中序遍历数组中，根结点的左边是左子数，左子数的区间在前序遍历数组中又可以知道左子数的根结点，在中序遍历数组中左子数的根结点右边的左子数的右子树，那么以此类推，可以唯一地确定二叉树的每个位置上的元素。
code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
left_inorder = inorder[:inorder.index(root.val)]
right_inorder = inorder[inorder.index(root.val)+1:]
l = len(left_inorder)
left_preorder = preorder[1:l+1]
right_preorder = preorder[l+1:]
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root
