题目

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

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

  1. 输入：root = [4,2,7,1,3], val = 5
  2. 输出：[4,2,7,1,3,5]
  3. 解释：另一个满足题目要求可以通过的树是：

image.png
示例 2：

  1. 输入：root = [40,20,60,10,30,50,70], val = 25
  2. 输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

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

提示：

  • 树中的节点数将在 [0, 10^4]的范围内。
  • -10^8 <= Node.val <= 10^8
  • 所有值 Node.val 是 独一无二 的。
  • -10^8 <= val <= 10^8

  • 保证 val 在原始BST中不存在。

    解题方法

    迭代

    迭代遍历数组，直到寻找到空位置，在该位置插入元素即可。
    时间复杂的O(n)，空间复杂的O(1)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   TreeNode* insertIntoBST(TreeNode* root, int val) {
    15.       TreeNode* p = new TreeNode(val);
    16.       TreeNode* cur = root;
    17.       if(!cur)    return p;
    18.       while(cur) {
    19.           if(cur->val>val){
    20.               if(cur->left)   cur = cur->left;
    21.               else {
    22.                   cur->left = p;
    23.                   return root;
    24.               }
    25.           }
    26.           if(cur->val<val){
    27.               if(cur->right)   cur = cur->right;
    28.               else {
    29.                   cur->right = p;
    30.                   return root;
    31.               }
    32.           }
    33.       }
    35.       return root;
    36.   }
    37. };

    递归

    上述方法采用递归实现，递归至空节点后插入，否则返回当前节点。
    时间复杂的O(n)，空间复杂的O(n)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   TreeNode* insertIntoBST(TreeNode* root, int val) {
    15.       if(!root) return new TreeNode(val);
    17.       if(root->val>val)  root->left = insertIntoBST(root->left, val);
    18.       if(root->val<val)  root->right = insertIntoBST(root->right, val);
    20.       return root;
    21.   }
    22. };