石河子做网站,wordpress自动电影釆集,网站的网站建设公司,如何用微信支付购物网站235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了#xff0c;因为 可以利用二叉搜索树的特性无需全部遍历。特点#xff1a;当前节点在p#xff0c;q节点之前则必为最近公共祖先 class Solution {public TreeNode lowestCommonAncestor(TreeNo… 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了因为 可以利用二叉搜索树的特性无需全部遍历。特点当前节点在pq节点之前则必为最近公共祖先 class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null){return root;}//当前节点大于pq节点值往当前节点左子树遍历if(root.val p.val root.val q.val){TreeNode left lowestCommonAncestor(root.left,p,q);if(left ! null){return left;}}//当前节点小于pq节点值往当前节点右子树遍历if(root.val q.val root.val p.val){TreeNode right lowestCommonAncestor(root.right,p,q);if(right ! null){return right;}}//如果当前节点值在两个节点值中间这就是最近公共祖先if(root.val p.val root.val q.val){return root;}return root;}
} 迭代法 class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root ! null){//p,q节点都在左if(root.val p.val root.val q.val){root root.left;//p,q节点都在右}else if(root.val q.val root.val p.val){root root.right;//当前节点在p,q中间}else{return root;}}return root;}
} 701.二叉搜索树中的插入操作 思路只需要在叶子节点上可以找到我们要插入的新节点位置向上放回新节点给上一个节点进行操作 通过递归函数返回值完成了新加入节点的父子关系赋值操作了下一层将加入节点返回本层用root-left或者root-right将其接住。 class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//递归终止条件 递归到叶子节点 创建新节点返回给上一个节点if(root null){return new TreeNode(val);}//当前节点值大于val 将新节点插入当前节点的左侧if(root.val val){root.left insertIntoBST(root.left,val);}if(root.val val){root.right insertIntoBST(root.right,val);}return root;}
} 450.删除二叉搜索树中的节点 五种情况 1.没找到删除节点遍历到空节点直接返回 2.遍历到删除节点删除节点左右子树为空向上返回null 3.遍历到删除节点删除节点左子树为空右子树不为空 返回右子树节点 4.遍历到删除节点删除节点左子树不为空右子树为空 返回左子树节点 5.遍历到删除节点删除节点左右子树都不为空 将删除节点左子树头节点放到删除节点右子树下最左面节点的左孩子上返回删除节点右孩子为新的根节点 class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件找到删除节点 执行删除节点逻辑 将删除完的操作节点返回给上一个节点//没有找到删除节点if(root null){return root;}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 cur root.right;while(cur.left ! null){cur cur.left;}//再将删除节点的左子树连接到curcur.left root.left;//此处逻辑为 左为空 右不为空逻辑 直接返回右孩子return root.right; //直接将父节点指向删除节点的右孩子 删除节点}}//单层递归逻辑if(root.val key){root.left deleteNode(root.left,key);}if(root.val key){root.right deleteNode(root.right,key);}return root;}
}
