Number of Ways to Reorder Array to Get Same BST LeetCode solution in Python

1
# Runtime: 556 ms (Top 18.24%) | Memory: 15.4 MB (Top 89.19%)
2
class node:
3
    def __init__(self, val):
4
        self.val = val
5
        self.left = None
6
        self.right = None
7

8

9
class Solution:
10
    def BST(self, root, cur):
11
        if cur.val < root.val:
12
            if root.left == None:
13
                root.left = cur
14
                return
15
            else:
16
                self.BST(root.left, cur)
17
        elif cur.val > root.val:
18
            if root.right == None:
19
                root.right = cur
20
                return
21
            else:
22
                self.BST(root.right, cur)
23

24
    def solve(self, root):
25
        if root.left == None and root.right == None:
26
            return 1
27
        left = 0
28
        right = 0
29
        if root.left is not None:
30
            left = self.solve(root.left)
31
        if root.right is not None:
32
            right = self.solve(root.right)
33
        self.total *= math.comb(left + right, left)
34
        return left + right + 1
35

36
    def numOfWays(self, nums: List[int]) -> int:
37
        import math
38

39
        self.total = 1
40
        root = node(nums[0])
41
        for i in range(1, len(nums)):
42
            self.BST(root, node(nums[i]))
43
        self.solve(root)
44
        return (self.total - 1) % (int(1e9) + 7)