哈尔滨免费建站模板,曹县住房和城乡建设部网站,wordpress 影音插件,跨境电商网站建设主管岗位职责目录 一、力扣235.二叉搜索树的最近公共祖先1.1 题目1.2 思路1.3 代码 二、力扣701.二叉搜索树中的插入操作2.1 题目2.2 思路2.3 代码 三、力扣450.删除二叉搜索树中的节点3.1 题目3.2 思路3.3 代码3.4 总结 一、力扣235.二叉搜索树的最近公共祖先
1.1 题目 1.2 思路
利用二叉… 目录 一、力扣235.二叉搜索树的最近公共祖先1.1 题目1.2 思路1.3 代码 二、力扣701.二叉搜索树中的插入操作2.1 题目2.2 思路2.3 代码 三、力扣450.删除二叉搜索树中的节点3.1 题目3.2 思路3.3 代码3.4 总结 一、力扣235.二叉搜索树的最近公共祖先
1.1 题目 1.2 思路
利用二叉搜索树的有序特性来实现 如果cur大于pq向左搜索 如果cur小于pq向右搜索 如果介于两者之间则找到
1.3 代码
递归法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归法if(root null){return null;}return traversal(root,p,q);}public TreeNode traversal(TreeNode root,TreeNode p,TreeNode q){//和上题类似第二种情况也包含在了处理逻辑里if(root.val p.val root.val q.val){return traversal(root.right,p,q);}if(root.val p.val root.val q.val){return traversal(root.left,p,q);}//当前节点介于[p,q] 闭区间return root;}
}迭代法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//迭代if(root null){return null;}TreeNode cur root;while(true){if(cur.val p.val cur.val q.val){cur cur.left;continue;}if(cur.val p.val cur.val q.val){cur cur.right;continue;}return cur;}}
}二、力扣701.二叉搜索树中的插入操作
2.1 题目 2.2 思路
根据二叉搜索树的特性比大小向下遍历直到找到null将其new一个新的结点插入进去。
2.3 代码
自己的思路
class Solution {public TreeNode newnode;public TreeNode insertIntoBST(TreeNode root, int val) {//比大小来遍历寻找该插入的位置if(root null){return new TreeNode(val);}traversal(root,val);return root;}public void traversal(TreeNode root,int val){if(val root.val){if(root.right null){newnode new TreeNode(val);root.right newnode;return;}traversal(root.right,val);}if(val root.val){if(root.left null){newnode new TreeNode(val);root.left newnode;return;}traversal(root.left,val);}}
}三、力扣450.删除二叉搜索树中的节点
3.1 题目 3.2 思路
梳理本题的五种情况 1没有找到该节点 2找到了该节点该节点的左右孩子均为空 3找到了该节点该节点的左孩子为空右孩子不为空 4找到了该节点该节点的左孩子不为空右孩子为空 5找到了该节点该节点的左右孩子均不为空最关机键的点见下图
3.3 代码
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//确定递归的终止条件//没有找到该节点if(root null){return null;}//找到了该节点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{//假设root的右子树上位,那么需要将root的左子树插入root的右子树中再返回右子树TreeNode cur root.right;while(cur.left ! null){cur cur.left;}cur.left root.left;return root.right;}}//单层递归逻辑if(key root.val){root.right deleteNode(root.right,key);}if(key root.val){root.left deleteNode(root.left,key);}return root;}
}3.4 总结
1五种情况的分析递归终止条件 2不用双指针pre而是将处理后的结点回溯返回给上层节点接住。单层递归逻辑
