《Leetcode of September 》701. 二叉搜索树中的插入操作

# 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)
        
        #如果插入的节点是大于根节点，那肯定是在右子树插
        if root.val<val:
            #如果右子树是空，直接插入；否则递归的去插入右子树
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insertIntoBST(root.right,val)
            
        #如果插入节点的值是小于根节点，那同理可得
        if root.val>val:
            if not root.left:
                root.left  = TreeNode(val)
            else:    
                self.insertIntoBST(root.left,val)
            
        
        return root

首先关于树的题目尽量用递归去解决，因为树的定义就是用递归定义的 其次这是一个二叉搜索树，其特点就是中序遍历是一个严格的递增数列 利用其性质，然后判断根节点和要插入的关系，调用递归去插入 如果大于根节点那就在右子树插入并且如果右子树为空，直接插入；否则递归 如果小于根节点那就在左子树插入并且如果左子树为空，直接插入；否则递归 返回树

总结：充分利用二叉搜索树的性质和递归。