Leetcode 925 Solution

This article provides solution to leetcode question 925 (construct-binary-tree-from-preorder-and-postorder-traversal)
Categories:
Tags:
Access this page by simply typing in "lcs 925" in your browser address bar if you have bunnylol configured.

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)