跟随carl代码随想录刷题
语言：python

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

题目：给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

题目分析

本题不涉及调整二叉树的结构。
只要遇到空节点，将值插入进去即可。
⭐️二叉搜索树不用遍历整棵树，否则是对二叉搜索树的侮辱😆

完整代码如下

递归法——有返回值

# 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: Optional[TreeNode], val: int) -> Optional[TreeNode]:

        
        if not root:
            return TreeNode(val)  # 如果数为空，那val就作为根节点
        
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
            # root = root.left
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)
            # root = root.right
        return root

递归法——一种更简便的方式

# 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: Optional[TreeNode], val: int) -> Optional[TreeNode]:    
        newNode = TreeNode(val)
        if not root:
            return newNode  # 如果数为空，那val就作为根节点
        
        if not root.left and val < root.val:
            root.left = newNode
        if not root.right and val > root.val:
            root.right = newNode
        
        if val < root.val:
            self.insertIntoBST(root.left, val)
        if val > root.val:
            self.insertIntoBST(root.right, val)
        
        return root

迭代法

# 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: Optional[TreeNode], val: int) -> Optional[TreeNode]:    
        if not root:
            return TreeNode(val)  # 如果数为空，那val就作为根节点
        
        parent = None
        cur = root
        
        while cur:
            if cur.val > val:
                parent = cur
                cur = cur.left
            elif cur.val < val:
                parent = cur
                cur = cur.right
        if parent.val > val:
            parent.left = TreeNode(val)
        else:
            parent.right = TreeNode(val)
        
        return root