Question Link:
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
The basic idea is same to that of Construct Binary Tree from Inorder and Postorder Traversal.
We solve it using a recursive function.
First, we find preorder[0] in inorder, let’s say inorder[i] == preorder,
then construct the left tree from preorder[1..i] and inorder[0..i-1]
and the right tree from preorder[i+1..n-1] and inorder[i+1..n-1].
The code is as follows.
[-]
Python code accepted by LeetCode OJ
Python code accepted by LeetCode OJ
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
def buildTree(self, preorder, inorder):
n = len(preorder)
if n == 0:
return None
elif n == 1:
return TreeNode(preorder[0])
else:
mid_inorder = inorder.index(preorder[0])
root = TreeNode(preorder[0])
root.left = self.buildTree(preorder[1:mid_inorder+1], inorder[:mid_inorder])
root.right = self.buildTree(preorder[mid_inorder+1:], inorder[mid_inorder+1:])
return root
近期评论