Leetcode 925 Solution

This article provides solution to leetcode question 925 (construct-binary-tree-from-preorder-and-postorder-traversal)

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

Solution

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode: def dfs(pre, post, i1, j1, i2, j2): if i1 > j1: return None
node = TreeNode(pre[i1]) if i1 == j1: return node
k = 0 while post[i2 + k] != pre[i1 + 1]: k += 1
print(i1, j1, i2, j2, k)
node.left = dfs(pre, post, i1 + 1, i1 + 1 + k, i2, i2 + k) node.right = dfs(pre, post, i1 + 1 + k + 1, j1, i2 + k + 1, j2 - 1)
return node
return dfs(pre, post, 0, len(pre) - 1, 0, len(post) - 1)