leetcode-solution/Python/0998-maximum-binary-tree-ii.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# time complexity: O(n)
# space complexity: O(n)
from typing import Optional


class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root and root.val > val:
            root.right = self.insertIntoMaxTree(root.right, val)
            return root
        node = TreeNode(val)
        node.left = root
        return node


root1 = TreeNode(4)
root1.left = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
val = 5
print(Solution().insertIntoMaxTree(root1, val))
root2 = TreeNode(5)
root2.left = TreeNode(2)
root2.right = TreeNode(4)
root2.left.right = TreeNode(1)
val = 3
print(Solution().insertIntoMaxTree(root2, val))
root3 = TreeNode(5)
root3.left = TreeNode(2)
root3.right = TreeNode(3)
root3.left.right = TreeNode(1)
val = 4
print(Solution().insertIntoMaxTree(root3, val))