二叉搜索树中的插入操作

题目描述

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

输入输出样例

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

具体插入方式如下图所示：

题解

首先思考，对应的节点该做什么事情。我们想把节点插入进行，并符合二叉树的规则。那么就是将val的值与root的左子树与右子树的值进行一个比较。遇到空的就插入,具体代码十分清晰。

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

        if (root->val > val) root->left = insertIntoBST(root->left,val);
        else if (root->val < val) root->right = insertIntoBST(root->right,val);
        return root;
    }
};