701. Insert into a Binary Search Tree

🟠   🔖  树 二叉搜索树 二叉树  🔗 LeetCode

题目

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5

Output: [4,2,7,1,3,5]

Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25

Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

Output: [4,2,7,1,3,5]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -10^8 <= Node.val <= 10^8
• All the values Node.val are unique.
• -10^8 <= val <= 10^8
• It's guaranteed that val does not exist in the original BST.

题目大意

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

解题思路

• 如果树为空（即根节点为 null），则新节点将成为树的根。
• 如果树不为空，我们从树的根节点开始，比较新节点的值与当前节点的值。
  • 如果新节点的值小于当前节点的值，则递归地将新节点插入到当前节点的左子树中。
  • 如果新节点的值大于当前节点的值，则递归地将新节点插入到当前节点的右子树中。

代码

/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  } else {
    root.right = insertIntoBST(root.right, val);
  }
  return root;
};

相关题目

相关题目

• 700. 二叉搜索树中的搜索

- [700. 二叉搜索树中的搜索](./0700.md)