二叉搜索树中的插入操作-二叉树701-python

没看答案，缺点是最坏情况下BST成了链表，改进是AVL(平衡BST)树。

# 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 insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        
        insert = root
        
        while True:
            if insert.val < val:
                if not insert.right:
                    insert.right = TreeNode(val)
                    break
                insert = insert.right
            elif insert.val > val:
                if not insert.left:
                    insert.left = TreeNode(val)
                    break
                insert = insert.left
        
        return root