- 分類：Tree
- 時(shí)間復(fù)雜度: O(n) 這種把樹的節(jié)點(diǎn)都遍歷一遍的情況時(shí)間復(fù)雜度為O(n)
- 空間復(fù)雜度: O(h) 樹的節(jié)點(diǎn)的深度
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
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
代碼：
# 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 preorder==None or inorder==None or len(preorder)!=len(inorder):
return None
return self.helper(preorder,inorder,0,0,len(inorder)-1)
def helper(self,preorder,inorder,pre_st,in_st,in_ed):
if pre_st>=len(preorder) or in_st>in_ed:
return
root=TreeNode(preorder[pre_st])
for i in range(in_st,in_ed+1):
if inorder[i]==preorder[pre_st]:
break
root.left=self.helper(preorder,inorder,pre_st+1,in_st,i-1)
root.right=self.helper(preorder,inorder,pre_st+(i-in_st)+1,i+1,in_ed)
return root
討論：
1.考察前序遍歷和中序遍歷的特點(diǎn)，利用遞歸/分治來解這道題
2.注意幾個(gè)位置，一個(gè)pre_st躏结，一個(gè)in_st,in_ed
