leetcode_701. 二叉搜索树中的插入操作（C++）

题目

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

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

例如,

给定二叉搜索树:

4
   / 
  2   7
 / 
1   3
和 插入的值: 5

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

4
   /   
  2     7
 /    /
1   3 5

或者这个树也是有效的:

5
   /   
  2     7
 /    
1   3
     
      4

思路

二叉搜索树：

左子树皆比根节点小 右子树皆比根节点大

利用这个性质，我们可以很容易地想出思路：

如果树为空，直接返回这个节点（也就是以这个节点为根的树） 当前值大于根，递归右子树 否则，递归左子树 最后（递归完毕后）的返回值即为根节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
          
   
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
          
   
        if(!root) return new TreeNode(val); 
        if(val > root -> val)
            root -> right = insertIntoBST(root -> right, val);
        else root -> left = insertIntoBST(root -> left, val);
        return root;
    }
};