Maximum Binary Tree II LeetCode solution in Python

1
class Solution:
2
    """
3
    approach:
4
    given a, we can get the inorder traversal of it, then append val to it and
5
    then construct the tree back
6
    """
7

8
    def insertIntoMaxTree(
9
        self, root: Optional[TreeNode], val: int
10
    ) -> Optional[TreeNode]:
11
        inorder_list = []
12

13
        def inorder(root):
14
            if not root:
15
                return
16
            inorder(root.left)
17
            inorder_list.append(root.val)
18
            inorder(root.right)
19

20
        inorder(root)
21
        inorder_list.append(val)
22

23
        def get_maximum(val_list):
24
            max_index = -1
25
            max_val = -1
26
            for i, val in enumerate(val_list):
27
                if val > max_val:
28
                    max_val = val
29
                    max_index = i
30
            return max_index, max_val
31

32
        def create_tree(val_list):
33
            if not len(val_list):
34
                return None
35
            index, val = get_maximum(val_list)
36
            node = TreeNode(val)
37
            node.left = create_tree(val_list[:index])
38
            node.right = create_tree(val_list[index + 1 :])
39
            return node
40

41
        b = create_tree(inorder_list)
42
        return b