Leetcode701. 二叉搜索树中的插入操作（insert-into-a-binary-search-tree）

快来打我* 2022-12-11 12:24 173阅读 0赞

# 二叉搜索树中的插入操作 #

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

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

例如,

给定二叉搜索树:

4
       / \
      2   7
     / \
    1   3

和 插入的值: 5  
你可以返回这个二叉搜索树:

4
       /   \
      2     7
     / \   /
    1   3 5

或者这个树也是有效的:

5
       /   \
      2     7
     / \   
    1   3
         \
          4

提示：

*  给定的树上的节点数介于 `0` 和 `10^4` 之间
 *  每个节点都有一个唯一整数值，取值范围从 `0` 到 `10^8`
 *  `-10^8 <= val <= 10^8`
 *  新值和原始二叉搜索树中的任意节点值都不同

# 代码与思路 #

## 迭代法 ##

*  如果 root 是空，则新建树节点作为根节点返回即可。
 *  否则：  
    1.初始化 cur 指向 root。  
    2.比较 cur.val 与目标值的大小关系：  
    　　如果 cur.val 大于目标值，说明目标值应当插入 cur 的左子树中，如果 cur.left 为 null，表明这是目标值可以插入的位置，直接 插入并返回即可；否则 cur 指向 cur.left，重复步骤 2；  
    　　如果 cur.val 小于目标值，说明目标值应当插入 cur 的右子树中。如果 cur.right 为 null，表明这是目标值可以插入的位置，直接插入并返回即可；否则 cur 指向 cur.right，重复步骤 2。

/** * 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) { 
            TreeNode node = new TreeNode(val);
            if (root == null) { 
                return node;
            }
    
            TreeNode cur = root;
            while (true) { 
                if (cur.val > val) { 
                    if (cur.left == null) { 
                        cur.left = node;
                        break;
                    }
                    cur = cur.left;
                } else { 
                    if (cur.right == null) { 
                        cur.right = node;
                        break;
                    } 
                    cur = cur.right;
                }
            }
            return root;
        }
    }

## 递归法 ##

*  如果 root 是空，则新建树节点作为根节点返回即可。  
    否则比较 root.val 与目标值的大小关系：
 *  如果 root.val 大于目标值，说明目标值应当插入 root 的左子树中，问题变为了在 root.left 中插入目标值，递归调用当前函数；
 *  如果 root.val 小于目标值，说明目标值应当插入 root 的右子树中，问题变为了在 root.right 中插入目标值，递归调用当前函数。

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 { 
                root.left = insertIntoBST(root.left, val);
            }
            return root;
        }
    }

[转自sweetiee][sweetiee]

[sweetiee]: https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/solution/2-de-cha-ru-by-sweetiee/