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

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

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

示例 1：

img

1
2
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

迭代法里面的双指针值得学习

Solution

迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val); // 如果树为空，新值成为树的根节点。
        TreeNode newRoot = root; // 保存根节点引用，以便最后返回。
        TreeNode pre = root;     // 用来追踪当前节点的前一个节点。
        
        while (root != null) {
            pre = root; // 更新前一个节点
            if (root.val > val) { // 如果当前节点的值大于插入值，向左走
                root = root.left;
            } else if (root.val < val) { // 如果当前节点的值小于插入值，向右走
                root = root.right;
            }
        }
        // 循环结束时，pre 指向插入位置的父节点
        if (pre.val > val) {
            pre.left = new TreeNode(val); // 如果父节点的值大于插入值，插入到左子树
        } else {
            pre.right = new TreeNode(val); // 否则，插入到右子树
        }

        return newRoot; // 返回根节点，这个根节点没有改变。
    }
}

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) { // 如果当前节点为空，找到了插入位置
            return new TreeNode(val);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val); // 如果当前节点的值小于要插入的值，递归到右子树
        } else if (root.val > val) {
            root.left = insertIntoBST(root.left, val); // 如果当前节点的值大于要插入的值，递归到左子树
        }
        return root; // 返回修改后的当前节点
    }
}