# LeetCode: 998. 最大二叉树 II¶

## 1、题目描述¶

• 如果 A 为空，返回 null
• 否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
• 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).

输入：root = [4,1,3,null,null,2], val = 5



输入：root = [5,2,4,null,1], val = 3



输入：root = [5,2,3,null,1], val = 4



• 1 <= B.length <= 100

## 2、解题思路¶

• 分三种情况讨论

• 没有根节点

• 根节点小于val
• 需要找到插入点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
node = TreeNode(val)
if not root:
return node

if root.val < val:
node.left = root
return node

temp = root
while temp.right and temp.right.val > val:
temp = temp.right

node.left = temp.right
temp.right = node

return root

• 递归实现
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
node = TreeNode(val)
if not root:
return node

if root.val < val:
node.left = root
return node

root.right = self.insertIntoMaxTree(root.right, val)
return root