## Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]


Return the following binary tree:

    3
/ \
9  20
/  \
15   7


## Solutions

给定中序和后序遍历的结果，求先序遍历的结果。

### 1. 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

class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder:
return None

root_i = inorder.index(postorder[-1])
root = TreeNode(postorder[-1])
root.left = self.buildTree(inorder[:root_i], postorder[:root_i])
root.right = self.buildTree(inorder[root_i+1:], postorder[root_i:-1])

return root

# Runtime: 208 ms, faster than 23.80% of Python3 online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
# Memory Usage: 88.1 MB, less than 11.11% of Python3 online submissions for Construct Binary Tree from Inorder and Postorder Traversal.


### 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

class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if (not postorder) or (not inorder) or (len(postorder) != len(inorder)):
return None

d = dict()
for idx, val in enumerate(inorder):
d[val] = idx
for i in range(len(inorder) - 2, -1, -1):
val = postorder[i]
node = TreeNode(val)
if d[val] > d[stack[-1].val]:
stack[-1].right = node
else:
while stack and d[val] < d[stack[-1].val]:
parent = stack.pop()
parent.left = node
stack.append(node)
# Runtime: 60 ms, faster than 94.62% of Python3 online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
# Memory Usage: 15.1 MB, less than 100.00% of Python3 online submissions for Construct Binary Tree from Inorder and Postorder Traversal.