java算法day20

java算法day20

• 701.二叉搜索树中的插入操作
• 450.删除二叉搜索树中的节点
• 108 将有序数组转换为二叉搜索树

---

本次的题目都是用递归函数的返回值来完成，多熟悉这样的用法，很方便。
其实我感觉，涉及构造二叉树的题目，用递归函数的返回值来做比较方便。每一层涉及对本层的构造，本层的操作结束后，是通过root.left = dfs(root.left,…)这样的方式来递归。
通过这种方式，到最后一层递归好之后，向上返回，这样树就构建起来了。

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;}
}

---

450.删除二叉搜索树中的节点

这个就像手算删除二叉树节点的过程。删的时候判断属于哪种类型。
这里就把所有类型做一个判断，符合哪种就完成哪种删除，这就是本题的思路。
有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

第五种比较抽象，但是这就是调整的方式，可以看看下图。
根据BST的性质，就是要把左子树挂到右子树最左下，才符合BST的性质。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//这个情况就属于没搜到，到了最底下就返回了，一直把null带给最顶层。if(root==null){return root;}//每到一个节点就先做判断，是不是要删的节点，不是再按BST往下层走if(root.val==key){//开始分情况讨论了，先拿下比较简单的情况if(root.left == null){//删除的节点，左子树为空，那么就把右子树挂上去，即把右子树返回给上层return root.right;}else if(root.right==null){return root.left;}else{TreeNode cur = root.right;while(cur.left!=null){cur = cur.left;}//此时已经到右子树的最左了，把root的左子树直接挂到cur的左子树上cur.left = root.left;//然后删除当前节点，root直接指向root.right就完成删除了root = root.right;//这里就完成了删除操作，然后返回结果。return root;}}//BST向下搜索构建的过程//这里一定要想清楚，因为是BST，所以往下就一个方向，所以往下递归构建就一个方向，//在每一层要么往左构建，要么往右构建。//key>root.val那往右进行递归到下一层，构建本层的root.rightif(key>root.val){root.right = deleteNode(root.right,key);}else if(key<root.val){root.left = deleteNode(root.left,key);}//这里已经是回来的逻辑了，所以构建的结果要返回给上一层。return root;}
}

---

108 将有序数组转换为二叉搜索树

题目一旦涉及到数组，那么根据经验，尽量不要重新定义左右区间数组，而是用下标来操作原数组。

本题有个要点，那就要满足平衡二叉搜索树。
因为对于有序数组而言，直接按顺序建一个线性树，那也满足二叉搜索树。

那要满足平衡二叉树那该怎么办？
本质是在找分割点。
递归的过程种，每次分割点取数组中间节点，然后递归构建左右子树就行了。
所以一层的子区间可以通过传递下标来完成表示。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums,0,nums.length-1);}TreeNode traversal(int[] nums,int left,int right){//递归出口，也就是递归构造的过程是区间不断收缩的过程，收缩完了就代表该位置没有节点构造。if(left>right){return null;}//每次取中间节点作为分割点int mid = left+(right-left)/2;//构造新节点TreeNode root = new TreeNode(nums[mid]);//递归构造左右子树，传递子区间。因为节点要取新的区间的中间节点。//这里显然是左闭右闭写法。root.left = traversal(nums,left,mid-1);root.right = traversal(nums,mid+1,right);//构造完了就返回，从底下返回来上，就全都构建好了。return root;}
}