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

题目描述

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

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

例如,

给定二叉搜索树:
4
/ \ 2 7
/ \ 1 3
和插入的值: 5

你可以返回这个二叉搜索树:

4
/ \ 2 7
/ \ /
1 3 5

或者这个树也是有效的:

5
/ \ 2 7
/ \ 1 3
\ 4

来源：LeetCode

思路

插入节点是建一棵二叉搜索树的基本操作，不多叙述了。此题关键点在于不影响原始二叉搜索树，所以每次要新创建一个节点。

解法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
const insertIntoBST = (root, val) => {
  if (!root) {
    return new TreeNode(val);
  }

  const newRoot = new TreeNode(root.val);
  newRoot.left = root.left;
  newRoot.right = root.right;

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

  return newRoot;
};