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.