golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2022-08-30 11:44:50

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
    var parent *TreeNode
    for cur := root; cur != nil; cur = cur.Right {
        if val > cur.Val {
            if parent == nil {
                return &TreeNode{val, root, nil}
            }
            parent.Right = &TreeNode{val, cur, nil}
            return root
        }
        parent = cur
    }
    parent.Right = &TreeNode{Val: val}
    return root
}

python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-08-30 11:44:14

# 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
'''
如果根节点的值小于给定的整数 val，那么新的树会以 val 作为根节点，并将原来的树作为新的根节点的左子树。

否则，我们从根节点开始不断地向右子节点进行遍历。这是因为，当遍历到的节点的值大于 val 时，
由于 val 是新添加的位于数组末尾的元素，那么在构造的结果中，val 一定出现在该节点的右子树中。

当我们遍历到节点 cur 以及它的父节点 parent，并且 cur 节点的值小于 val 时，我们就可以停止遍历，
构造一个新的节点，以 val 为值且以 cur 为左子树。我们将该节点作为 parent 的新的右节点，并返回根节点作为答案即可。

如果遍历完成之后，仍然没有找到比 val 值小的节点，那么我们构造一个新的节点，以 val 为值，
将该节点作为 parent 的右节点，并返回根节点作为答案即可。
'''
class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        parent, cur = None, root
        while cur:
            if val > cur.val:
                if not parent:
                    return TreeNode(val, root, None)
                node = TreeNode(val, cur, None)
                parent.right = node
                return root
            else:
                parent = cur
                cur = cur.right
        
        parent.right = TreeNode(val)
        return root