【算法题解】60. 二叉搜索树中的插入操作

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/insert-into-a-binary-search-tree/

❞

题目

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。

返回插入后二叉搜索树的根节点。输入数据 「保证」 新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 「任意有效的结果」 。

示例 1：

输入：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]

提示：

树中的节点数将在的范围内。
所有值 Node.val 是独一无二的。
保证在原始BST中不存在。

什么是二叉树搜索树

解题之前需要先了解一下什么是 「二叉搜索树」。

二叉搜索树首先肯定得先是一颗二叉树，然后在此基础上呢还需要满足以下几点要求：

左子树的节点都要 「小于等于」 根节点。
右子树的节点都要 「大于等于」 根节点。
所有子树也都同样需要满足上面两点，也就是说二叉搜索树的任意子树同样也还是二叉搜索树。

如下图所示：从图中可以很容易的看出：「二叉搜索树的中序遍历必然是一个有序序列」。如上图中二叉搜索树的中序遍历为。

根据上述定义我们也可以很清楚的知道它为啥叫二叉搜索树了。当我们使用二叉搜索树来检索一个值的时候，「只要不断的和当前根节点的值比较即可」，就可以立即排除掉一半的节点，效率非常高。普通二叉树是做不到这一点的，必须一个节点一个节点的去找，不管是深度优先还是广度优先。

题解

根据二叉搜索树的定义，如果要插入一个节点，我们需要将其和根节点对比一下：

如果比根节点大就往右边走，向右子树插入。如果没有右子树，那么这个新插入的节点就是右子树。
如果比根节点小就往左边走，向左子树插入。如果没有左子树，那么这个新插入的节点就是左子树。
不管是往左走还是往右走，左右子树同样是二叉搜索树，所以重复上面两个步骤。

根据上面列出来的思路，判断条件后是求子问题，可以使用「递归」来解题。

边界条件：当左或者右子树为空的时候，递归结束。用待插入的值创建一个新的节点把空位补上即可。

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }

        if(val < root.val){
            root.left = insertIntoBST(root.left, val);
        }else{
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {

    if root == nil {
        return &TreeNode{Val: val}
    }

    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    }else {
        root.Right = insertIntoBST(root.Right, val)
    }

    return root
}