Construct Binary Tree from Inorder and Postorder Traversal LeetCode solution in Python

1
import bisect
2

3

4
# Definition for a binary tree node.
5
# class TreeNode(object):
6
#     def __init__(self, val=0, left=None, right=None):
7
#         self.val = val
8
#         self.left = left
9
#         self.right = right
10
class Solution(object):
11

12
    def buildTree(self, inorder, postorder):
13
        """
14
         7
15
          2
16
        -8
17
         :type inorder: List[int]
18
         :type postorder: List[int]
19
         :rtype: TreeNode
20
         ([-4,-10,3,-1], [7]) ((11,-8,2), [7])
21
        """
22
        currentSplits = [(inorder, [], [])]
23
        nodeDirectory = {}
24
        finalSplits = []
25
        for nodeVal in reversed(postorder):
26
            nodeDirectory[nodeVal] = TreeNode(nodeVal)
27
            for splits, nodes, directions in reversed(currentSplits):
28
                removing = None
29
                if nodeVal in splits:
30
                    removing = (splits, nodes, directions)
31
                    left = splits[: splits.index(nodeVal)]
32
                    right = splits[splits.index(nodeVal) + 1 :]
33
                    currentSplits.append(
34
                        (left, nodes + [nodeVal], directions + ["left"])
35
                    )
36
                    if len(left) <= 1:
37
                        finalSplits.append(
38
                            (left, nodes + [nodeVal], directions + ["left"])
39
                        )
40
                    currentSplits.append(
41
                        (right, nodes + [nodeVal], directions + ["right"])
42
                    )
43
                    if len(right) <= 1:
44
                        finalSplits.append(
45
                            (right, nodes + [nodeVal], directions + ["right"])
46
                        )
47
                    break
48
                if removing:
49
                    currentSplits.remove(removing)
50
        finalSplits = [splits for splits in finalSplits if splits[0]]
51

52
        while finalSplits:
53
            nodeVal, nodes, directions = finalSplits.pop()
54
            bottomNode = nodeDirectory[nodeVal[0]] if nodeVal else None
55
            while nodes:
56
                attachingNode = nodeDirectory[nodes.pop()]
57
                attachingDir = directions.pop()
58
                if attachingDir == "left":
59
                    attachingNode.left = bottomNode
60
                else:
61
                    attachingNode.right = bottomNode
62
                bottomNode = attachingNode
63
        return nodeDirectory[postorder[-1]]