网站首页样式,商务网站建设pdf,用php做一网站,建筑规范查询网代码随想录第二十二天 Leetcode 235. 二叉搜索树的最近公共祖先Leetcode 701. 二叉搜索树中的插入操作Leetcode 450. 删除二叉搜索树中的节点 Leetcode 235. 二叉搜索树的最近公共祖先
题目链接: 二叉搜索树的最近公共祖先 自己的思路:乍一看和二叉树的最近公共祖先类似#… 代码随想录第二十二天 Leetcode 235. 二叉搜索树的最近公共祖先Leetcode 701. 二叉搜索树中的插入操作Leetcode 450. 删除二叉搜索树中的节点 Leetcode 235. 二叉搜索树的最近公共祖先
题目链接: 二叉搜索树的最近公共祖先 自己的思路:乍一看和二叉树的最近公共祖先类似使用那个题的代码确实可以写出来但是没有利用到二叉搜索树的性质我们可以找出p和q结点值的较大者和较小者遍历整个二叉树如果出现了某个结点值位于两者之间就是我们要找的结点递归三部曲1、终止条件如果找到了位于两者之间的结点值直接返回结点即可2、传入参数当前结点p和q结点和最大值和最小值3、单层逻辑如果当前结点值大于最大值向左递归如果小于则向右递归否则返回当前节点
正确思路:递归
代码:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {int max p.valq.val?p.val:q.val;int min p.valq.val?p.val:q.val;return lowestCommonAncestor_new(root,p,q,max,min);}public TreeNode lowestCommonAncestor_new(TreeNode root,TreeNode p,TreeNode q,int max,int min){if (root.valminroot.valmax) return root;else if (root.valmax) return lowestCommonAncestor_new(root.left,p,q,max,min);else if (root.valmin) return lowestCommonAncestor_new(root.right,p,q,max,min);return root; }
}复杂度分析 时间复杂度 O ( n ) \mathcal{O}(n) O(n) 空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
Leetcode 701. 二叉搜索树中的插入操作
题目链接: 二叉搜索树中的插入操作 自己的思路:没想到
正确思路:这道题不要想复杂了只需要把要插入的元素插入到叶子节点就可以想通这点就可以了递归三部曲1、传入参数和返回值当前节点、插入的节点值返回插入之后的树的根节点2、终止条件当当前节点为空的时候返回新建的节点返回到上一个节点的左或者右节点具体看下面3、单层逻辑当当前节点的值大于val的话说明要插到左子树里面返回值为root.left因为是插到root的左子树里否则插到右子树里然后返回当前结点
代码:
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//插入到叶子节点上if (rootnull) return new TreeNode(val);//当前节点的值大于val就插到左子树上if (root.valval){root.left insertIntoBST(root.left,val);}if (root.valval){root.right insertIntoBST(root.right,val);}return root;}
}复杂度分析 时间复杂度 O ( n ) \mathcal{O}(n) O(n) 空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
Leetcode 450. 删除二叉搜索树中的节点
题目链接: 删除二叉搜索树中的节点 自己的思路:没想到
正确思路:本题并不是遍历整个二叉搜索树而是遍历到符合条件的二叉搜索树结点然后进行返回所以本题递归终止条件较为繁琐递归三部曲1、传入参数和返回值当前结点和key值返回参数为删除之后的树的根节点2、终止条件当当前节点为空的时候直接返回空当当前结点的值等于key的时候要分情况处理 ( 1 ) (1) (1):当当前节点为叶子节点时直接返回空 ( 2 ) (2) (2):当当前节点左节点为空时返回右节点 ( 3 ) (3) (3):当当前节点右节点为空时返回左节点 ( 4 ) (4) (4):当左节点不为空右节点也不为空时要进行树的变换我们以删除以后右节点上位为例那么删除以后的左节点会放到右子树的最左边的非空节点下面即可3、单层逻辑左右递归和二叉搜索树的插入类似
代码:
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件if (rootnull) return root;if (root.valkey){if (root.leftnullroot.rightnull) return null;else if (root.rightnull) return root.left;else if (root.leftnull) return root.right;else{TreeNode node root.right;while(node.left!null){node node.left;}node.left root.left;return root.right;}}//左右递归if (root.valkey) root.left deleteNode(root.left,key);if (root.valkey) root.right deleteNode(root.right,key);return root;}
}复杂度分析 时间复杂度 O ( n ) \mathcal{O}(n) O(n) 空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
