This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!
Problems
Construct Binary Tree from Inorder and Postorder Traversal
We want to return the binary tree by given inorder and postorder Traversal.
Approach
Postorder is left->right->root
and inorder is left->root->right
, so the root of tree is the rightmost of postorder traversal and we can get to know the subtree of it by checking inorder traversal.
For example:
inorder = 9,3,15,20,7 (left->root->right)
postorder = 9,15,7,20,3 (left->right->root)
The root is 3
because it is the rightmost in postorder traversal and the left subtree is 9
and the right subtree is 15, 20, 7
because in inorder Traversal, 9
is left of 3
(=root) and 15, 20, 7
is right of 3
. The next root is 20, and the right subtree is 15
and the left subtree is 7
.
So we are able to solve this question by repeating this process.
Solution
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(left_end, right_end):
if left_end > right_end:
return None
value = postorder.pop()
root = TreeNode(value)
index = index_map[value]
root.right = helper(index + 1, right_end)
root.left = helper(left_end, index - 1)
return root
index_map = {val:idx for idx, val in enumerate(inorder)}
return helper(0, len(inorder) - 1)
Thank you for reading this article!
I always welcome your feedback, question, and idea.
Top comments (0)