「每日LeetCode」2020年9月30日

本文最后更新于：2023年3月19日 晚上

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

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

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

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

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

1
2
3
4
5
4
   /   \
  2     7
 / \   /
1   3 5

或者这个树也是有效的:

1
2
3
4
5
6
7
5
   /   \
  2     7
 / \
1   3
     \
      4

提示：

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

思路

一开始想复杂了，认为要插入节点，同时保持平衡二叉树。该题简单递归设置即可，不断递归，直到要设值的点为 null，就可以插入值了。如果保持有序数组的平衡二叉树，需要中序遍历后获得数组，插入目标数组，再重新生成树。

解答

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
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function (root, val) {
  if (!root) {
    root = new TreeNode(val);
    return root;
  }
  if (root.val > val) {
    if (root.left) {
      insertIntoBST(root.left, val);
    } else {
      root.left = new TreeNode(val);
    }
  } else {
    if (root.right) {
      insertIntoBST(root.right, val);
    } else {
      root.right = new TreeNode(val);
    }
  }
  return root;
};