# 【LeetCode 701】二叉搜索树的插入操作
@[toc]
## 题目描述：
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
## 题目分析
1.二叉搜索树本身是一个二叉树，是递归定义的，因此在解题时较多地考虑用递归的思想；
2.二叉搜索树的特点在于左右子树的大小是严格限定的，对于一个父节点，其左儿子小于该父节点，右儿子大于该父节点。因此在插入时，考虑从根节点开始逐层与左右节点作比较，BFS（广度优先搜索）插入；
ps:当树不含有左右节点，即为空树时，直接插入即可。
## 题解代码
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
//比较大小作BFS
else if(root.val<val)root.right=insertIntoBST(root.right,val);
else root.left=insertIntoBST(root.left,val);
return root;
}
}
```
## 总结
本题也可以用迭代的写法，但考虑到二叉树本身的性质，做此类题一般用递归写法。
关键在于清楚二叉搜索树的性质，以及对BFS的思想的深入了解。
