최대 이진 트리 II

최대 트리는 모든 노드가 하위 트리의 다른 값보다 큰 값을 갖는 트리입니다.

최대 이진 트리의 root와 정수val가 제공됩니다.

previous problem 에서와 마찬가지로 주어진 트리는 다음 a 루틴을 사용하여 목록 root = Construct(a) ( Construct(a) )에서 재귀적으로 구성되었습니다.

a가 비어 있으면 null를 반환합니다.

그렇지 않으면 a[i]를 a의 가장 큰 요소로 둡니다. 값이 root 인 a[i] 노드를 생성합니다.

root의 왼쪽 자식은 Construct([a[0], a[1], ..., a[i - 1]])가 됩니다.

root의 오른쪽 자식은 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])가 됩니다.

반품 root .

a가 직접 제공되지 않았으며 루트 노드root = Construct(a)만 제공되었습니다.
b가 값 a가 추가된 val의 복사본이라고 가정합니다. b가 고유한 값을 갖는다는 것이 보장됩니다.

반품Construct(b) .

예 1:



입력: root = [4,1,3,null,null,2], val = 5
출력: [5,4,null,1,3,null,null,2]
설명: a = [1,4,2,3], b = [1,4,2,3,5]

예 2:



입력: root = [5,2,4,null,1], val = 3
출력: [5,2,4,null,1,null,3]
설명: a = [2,1,5,4], b = [2,1,5,4,3]

예 3:



입력: root = [5,2,3,null,1], val = 4
출력: [5,2,4,널,1,3]
설명: a = [2,1,5,3], b = [2,1,5,3,4]

제약:

트리의 노드 수가 [1, 100] 범위에 있습니다.

1 <= Node.val <= 100

트리의 모든 값이 고유합니다.

1 <= val <= 100

해결책:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        curr = TreeNode(val = val)
        if not root or val > root.val:
            curr.left = root
            root = curr
        else:
            root.right = self.insertIntoMaxTree(root.right, val)
        return root