给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
题解
如何找到二叉搜索树的插入位置？
插入后要使得插入后的二叉树的中序序列为递增，可以不考虑题目中提示所说的改变树的结构的插入方式，只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
–>小于根则往左子树找，大于根则往右子树找
1.终止条件：遇到空节点，此时可以插入，并将插入节点的值返回。return new TreeNode(val)
2.本层操作：往左走或往右走,根据插入元素的数值，决定递归方向，本层用root->left或者root->right将下一层节点接住
3.递归没有终止，本层需返回root节点给上一层
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) { //终止条件if(root==null) return new TreeNode(val);//向右子树递归，并且用root.right接住递归返回值if(root.val>val) root.left=insertIntoBST(root.left,val);else root.right=insertIntoBST(root.right,val);//归没有终止，本层需返回root节点给上一层return root;}
}
