企业网站建设规划书的内容,新开传奇网站发布站,wordpress如何把标签去掉,新开的网站怎么做推广目录
235. 二叉搜索树的最近公共祖先
1、递归实现
2、迭代法实现 701.二叉搜索树中的插入操作#xff08;递归实现#xff09;
450.删除二叉搜索树中的节点#xff08;递归实现#xff09; 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了…目录
235. 二叉搜索树的最近公共祖先
1、递归实现
2、迭代法实现 701.二叉搜索树中的插入操作递归实现
450.删除二叉搜索树中的节点递归实现 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了因为 可以利用二叉搜索树的特性。 题目链接/文章讲解代码随想录 题解思路 1、递归实现 迭代法和递归法实现的原理一致其实我觉得这种迭代法本质就是递归的方法只不过步骤不一样而已 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root ! null){if(root.val p.val root.val q.val){TreeNode left lowestCommonAncestor(root.left,p,q);if(left ! null) return left;}else if(root.val p.val root.val q.val){TreeNode right lowestCommonAncestor(root.right,p,q);if(right ! null) return right;}else{return root;}}return null;}
} 2、迭代法实现 迭代法和递归法实现的原理一致其实我觉得这种迭代法本质就是递归的方法只不过步骤不一样而已 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root ! null){if(root.val p.val root.val q.val){TreeNode left lowestCommonAncestor(root.left,p,q);if(left ! null) return left;}else if(root.val p.val root.val q.val){TreeNode right lowestCommonAncestor(root.right,p,q);if(right ! null) return right;}else{return root;}}return null;}
} 701.二叉搜索树中的插入操作递归实现 本题比想象中的简单大家可以先自己想一想应该怎么做然后看视频讲解就发现 本题为什么比较简单了。 题目链接/文章讲解代码随想录 题解思路 多听卡哥视频讲解在二叉树中插入操作就是构造二叉树一定能在叶子节点找到我们要插入的节点然后可以根据二叉搜索树的特性比较当前节点的val值和给定的val直接判断在其左子树还是右子树进行插入操作最后直接返回root节点就好没听卡哥讲解之前单纯一团糊浆第一感觉很复杂又是各种插入方式等等听完卡哥视频讲解完思路还是清晰的一刷一定要多听多看多刷把思路打开非科班转码确实有点痛苦真的就颠覆之前没有训练后的思考方法加油吧 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//第二步确定终止条件if(root null) return new TreeNode(val);;//第三步确定单层处理逻辑if(root.val val){root.left insertIntoBST(root.left,val); //直接根据二叉搜索树的特性比较当前节点的val值和给定的val直接判断在其左子树还是右子树进行插入操作}else if(root.val val){root.right insertIntoBST(root.right,val); //直接根据二叉搜索树的特性比较当前节点的val值和给定的val直接判断在其左子树还是右子树进行插入操作}return root;}}作者vansven-h
链接https://leetcode.cn/problems/insert-into-a-binary-search-tree/solution/701er-cha-sou-suo-shu-zhong-de-cha-ru-ca-fj39/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 450.删除二叉搜索树中的节点递归实现 相对于 插入操作本题就有难度了涉及到改树的结构 题目链接/文章讲解代码随想录 题解思路 主要是删除节点的情况存在五种不同情况需要根据不同情况进行一一处理具体的5种情况见下方注释代码我想说的是一刷还是要多看、多听卡哥视频、多刷把方法论掌握的融汇贯通才有资本自己去造轮子这些都是基础算法都没掌握怎么去谈更进阶的知识呢 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//第二步确定终止条件当找到五种不同情况的节点需要删除时此时就是遍历到的节点就是终止条件需要及时对找到的节点进行处理才行if(root null) return null; //第一种情况没找到要删除的节点直接返回null值即可else if(root.val key){ //以下四种情况都是在找到要删除节点的情况下进行讨论的if(root.left null root.right null) return null; //第二种情况删除的时叶子节点else if(root.left ! null root.right null) return root.left; //第三种情况删除左不为空右为空的节点else if(root.left null root.right ! null) return root.right;//第四种情况删除左为空右不为空的节点else{TreeNode current root.right; //第五种情况删除左不为空右不为空的节点根据二叉搜索树的特性需要一直搜索右子树的左节点一直其叶节点进行插入while( current.left ! null){current current.left;}current.left root.left;return root.right;}}//第三步确定单层处理逻辑根据二叉树的搜索特性直接比较当前遍历节点的val值和key值直接判断在其左子树还是右子树进行删除节点操作if(root.val key) root.left deleteNode(root.left,key);else if(root.val key) root.right deleteNode(root.right,key);return root;}
}
