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.
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
Solutions
从先序遍历和中序遍历得到对应的二叉树。
1. DFS-递归
需要留意一下 inorder 中找到的 index 和 preorder 左子树个数的关系,其实 inorder 中找到的 root 的 index 指向的就是 preorder 中 root 加上左子树的截止的位置(包含)。
# Time Complexity: O(n)
# Space Complexity: O(n)
# 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 or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
left_inorder = inorder[:index]
right_inorder = inorder[index+1:]
left_preorder = preorder[1:index+1]
right_preorder = preorder[index+1:]
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root
# Runtime: 192 ms, faster than 40.03% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 88.6 MB, less than 13.16% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
通过通过使用集合或者字典来优化速度,从提交的结果上看,使用字典会更快一些。
# 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:
map_inorder = {}
for i, val in enumerate(inorder):
map_inorder[val] = i
def recurse(low, high):
if low > high:
return None
x = TreeNode(preorder.pop(0))
mid = map_inorder[x.val]
x.left = recurse(low, mid-1)
x.right = recurse(mid+1, high)
return x
return recurse(0, len(inorder)-1)
2. DFS-递推
看到高分的解法:
# Time Complexity: O(n)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 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) or (not inorder) or (len(preorder) != len(inorder)):
return None
root = TreeNode(preorder[0])
stack, index = [root], 0
for i in range(1, len(preorder)):
curr, prev = TreeNode(preorder[i]), None
while stack and stack[-1].val == inorder[index]:
prev = stack.pop()
index += 1
if prev:
prev.right = curr
else:
stack[-1].left = curr
stack.append(curr)
return root
# Runtime: 60 ms, faster than 95.61% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 14.7 MB, less than 86.84% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.