leetcode：701. 二叉搜索树中的插入操作【bst的插入】

分析

注意，bst的插入直接插叶子
无需像删除一样重构的
这个需要注意

ac code

# 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)

        def dfs(node):
            if val <= node.val:
                # 直接插入叶子
                if not node.left:
                    node.left = TreeNode(val)
                # 放到下一层再说
                else:
                    dfs(node.left)
            else:
                if not node.right:
                    node.right = TreeNode(val)
                else:
                    dfs(node.right)
        dfs(root)
        return root

总结

bst插入常识