做教育培训网站公司,郑州的网站建设公司哪家好,厦门免费网站建设,wordpress 语言文件java算法day20
701.二叉搜索树中的插入操作450.删除二叉搜索树中的节点108 将有序数组转换为二叉搜索树 本次的题目都是用递归函数的返回值来完成#xff0c;多熟悉这样的用法#xff0c;很方便。 其实我感觉#xff0c;涉及构造二叉树的题目#xff0c;用递归函数的返回值…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(rootnull){TreeNode newNode new TreeNode(val);return newNode;}//按BST的性质进行往下搜索//但是这里的特点是不断的构造最后返回给上一层。是以构造的角度来看if(valroot.val){root.right insertIntoBST(root.right,val);}else{root.left insertIntoBST(root.left,val);}return root;}
}难点就在这种以构造左右子树的角度的题做少了可能想得到但是写不出。 解法2pre指针的思想
我一开始想用的这种做法但是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(rootnull){return root;}//每到一个节点就先做判断是不是要删的节点不是再按BST往下层走if(root.valkey){//开始分情况讨论了先拿下比较简单的情况if(root.left null){//删除的节点左子树为空那么就把右子树挂上去即把右子树返回给上层return root.right;}else if(root.rightnull){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所以往下就一个方向所以往下递归构建就一个方向//在每一层要么往左构建要么往右构建。//keyroot.val那往右进行递归到下一层构建本层的root.rightif(keyroot.val){root.right deleteNode(root.right,key);}else if(keyroot.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(leftright){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,mid1,right);//构造完了就返回从底下返回来上就全都构建好了。return root;}
}
