Question Link:
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
Divide-and-Conquer
This problem can be easily solved using recursive method.
By given the inorder and postorder lists of the tree, i.e. inorder[1..n] and postorder[1..n],
postorder[n] should be the root’s value, then we find the position of postorder[n] in inorder[1..n].
Suppose the position is i,
then postorder[1..i-1] and inorder[1..i-1] are the postorder and inorder lists of root’s left tree
and postorder[i..n-1] and inorder[i+1..n] are the postorder and inorder lists of root’s right tree.
So we can construct the tree recursively.
Python Implement
The code of the recursive function is as follows.
[-]
Python code accepted by LeetCode OJ
Python code accepted by LeetCode OJ
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param inorder, a list of integers
# @param postorder, a list of integers
# @return a tree node
def buildTree(self, inorder, postorder):
n = len(inorder)
if n == 0:
return None
elif n == 1:
return TreeNode(postorder[-1])
else:
root = TreeNode(postorder[-1])
mid_inorder = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:mid_inorder], postorder[:mid_inorder])
root.right = self.buildTree(inorder[mid_inorder+1:], postorder[mid_inorder:-1])
return root
近期评论