java算法day20
- 701.二叉搜索树中的插入操作
- 450.删除二叉搜索树中的节点
- 108 将有序数组转换为二叉搜索树
701.二叉搜索树中的插入操作
本题的特点是在递归出口。而又由这个递归出口，决定了递归的过程中应该干什么。
核心思路：
按BST的方式进行向下搜索，遇到空的位置就进行插入节点。
难点：
这个处理方式很重要。之前我想的是我干脆弄一个pre节点，这样方便我进行插入。但是这样逻辑就很难写。
所以就只能从递归构造左右子树的角度来做。
我说的构造就是这样
root.left = ?
root.right = ?
这样的方式。这样一旦遇到空，那么创建新节点，返回给上一层。这样root.left或者root.right就直接完成构造了。
所以就按这样的思路来。然后往下搜的时候肯定按BST的性质来往下递归。一旦当前节点大于root.val那么递归右子树。一旦往下层一走刚好碰到null，那么创建新节点，这个创建的新节点刚好就符合规则，挂到了这个正确的位置上。
所以说这样的递归方式已经决定好添加的这个节点的位置了，就等着到这个地方之后进行新节点的 创建。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//递归出口
//root为空，表示走到底了，按BST的性质，这个地方正式新节点的所在地，所以返回给上一层
if(root==null){
TreeNode newNode = new TreeNode(val);
return newNode;
}
//按BST的性质进行往下搜索
//但是这里的特点是，不断的构造，最后返回给上一层。是以构造的角度来看
if(val>root.val){
root.right = insertIntoBST(root.right,val);
}else{
root.left = insertIntoBST(root.left,val);
}
return root;
}
}
难点就在这种以构造左右子树的角度的题做少了，可能想得到，但是写不出。
解法2：pre指针的思想
我一开始想用的这种做法，但是pre我处理的并不好。
所以从这个题解来学习处理pre节点。
注意这个题是迭代法，也就是用循环了。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//注意这个并不是递归出口，这只是特判
if (root == null) return new TreeNode(val);
//pre初始化为root。
//newRoot是用来后面构造好了返回结果的。
TreeNode newRoot = root;
TreeNode pre = root;
//我个人感觉，怎样才能使得最后的时候，pre和cur一前一后？
//技巧：pre的状态变更在一开是就更新为cur，而cur的变更则是在做完操作之后才变更。而且要针对cur做循环跳出的判断，否则到最后的时候，cur又跳进去了，pre会和cur同步。这样cur才会比pre多走一步。
//内部的逻辑就是BST的向下搜索过程
while (root != null) {
pre = root;
if (root.val > val) {
root = root.left;
} else if (root.val < val) {
root = root.right;
}
}
//这里就是判断这个新节点是挂在左边还是右边，因为cur只管遇到null就停下来
if (pre.val > val) {
pre.left = new TreeNode(val);
} else {
pre.right = new TreeNode(val);
}
return newRoot;
}
}