题目（leecode T701）：

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

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

方法：本题是为一个二叉搜索树加入一个新的值，题目中说可以重构二叉树，但其实没有必要，我们只需要对现有的二叉树进行遍历，把值插在某个节点的孩子节点上就可以了。即不改变原有二叉树的初始结构，只是单纯的加入一个新的节点。下面进行递归三部曲的分析。

1：传入参数与返回值：首先传入的肯定树的节点指针，其次要传入我们要插入的值。返回类型就是树节点指针类型。

2：终止条件：当我们递归到NULL时，就可以将值构造成一个新的树节点，并将该节点插入到该空位置上。

3：单层处理逻辑：单层递归时我们需要判断当前root的val值与我们将要插入的val值的大小，如果val>root->val，那么遍历该root的右子树，如果val<root->val，那么遍历该root的左子树。

题解：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root->val > val) root->left = insertIntoBST(root->left, val);
        if(root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};