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
# 感觉这道题不是很难，这里我是让所有要插入的节点都放在叶子节点。
# 那么我们用递归遍历的时候根节点就有四种情况
# 1，根节点的值和插入节点的值。根节点大就插入到左子树，根节点小就插入到右子树
#  然后在判断左右子树是否为空，如果为空直接左右指针指向以要插入的值构造的节点。
#   否则就继续遍历。
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        # 首先需要判断根节点是否为空，如果为空就直接返回要插入的值构造的节点。
        if not root: return TreeNode(val)
        # 这里判断要插入的值是要插入到左子树还是右子树。
        if root.val >= val and root.left:
            self.insertIntoBST(root.left,val)
        elif root.val >= val and not root.left:
            root.left = TreeNode(val)
        if root.val < val and root.right:
            self.insertIntoBST(root.right,val)
        elif root.val < val and not root.right:
            root.right = TreeNode(val)
        return root