2024年7月22日
题235. 二叉搜索树的最近公共祖先
普通解法还是和普通的祖先一样求即可,再依据搜索树特性进行剪枝即可加速。
import java.util.*;
class Solution {
Vector<TreeNode> vec1;
Vector<TreeNode> vec2;
int flag1 = 0;
int flag2 = 0;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//把p和q的路径都打印出来,然后从头开始往后看,如果第n个开始不一样了,那么第n-1个节点就是祖先
vec1 = new Vector<>();
vec2 = new Vector<>();
digui1(root,p);
digui2(root,q);
int i=0;
if(root.val==p.val && p.val==q.val){
return root;
}
TreeNode pre = root;
while(true){
if(i==vec1.size()||i==vec2.size()){
break;
}
if(vec1.get(i).val==vec2.get(i).val){
pre = vec1.get(i);
}else{
break;
}
i+=1;
}
return pre;
}
public void digui1(TreeNode root, TreeNode t){
if(flag1==1){
return;
}
if(root==null){
//回溯
return;
}
vec1.add(root);
if(root.val==t.val){
flag1=1;
return;
}
if(t.val>root.val){
digui1(root.right,t);
}else{
digui1(root.left,t);
}
if(flag1==0){
vec1.remove(vec1.size()-1);
}
return;
}
public void digui2(TreeNode root, TreeNode t){
if(flag2==1){
return;
}
if(root==null){
//回溯
return;
}
vec2.add(root);
if(root.val==t.val){
flag2=1;
return;
}
if(t.val>root.val){
digui2(root.right,t);
}else{
digui2(root.left,t);
}
if(flag2==0){
vec2.remove(vec2.size()-1);
}
return;
}
}
可以背一下高效迭代法,很好理解:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果一起大于或者小于,就更新当前节点,如果一起等于或者一个大一个小于就统一返回root即可
while (root != null) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
return root;
}
}
题701. 二叉搜索树中的插入操作
递归即可。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
return new TreeNode(val);
}
if(val>root.val){
root.right = digui(root.right,val);
}else{
root.left = digui(root.left,val);
}
return root;
}
public TreeNode digui(TreeNode p, int val){
if(p==null){
return new TreeNode(val);
}else{
if(val>p.val){
p.right = digui(p.right,val);
}else{
p.left = digui(p.left,val);
}
return p;
}
}
}
题450. 删除二叉搜索树中的节点
分类思考,递归多想一下就熟悉了,关键是处理左右子树都在的情况下,就是把左子树挪到右子树的最左下角即可。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = del(root,key);
return root;
}
public TreeNode del(TreeNode root, int val){
if(root==null){
return null;
}else if(val>root.val){
root.right = del(root.right,val);
return root;
}else if(val<root.val){
root.left = del(root.left,val);
return root;
}else{
//左右子树都空
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;
}
cur.left = root.left;
return root.right;
}
}
}
}
标签:right,TreeNode,val,随想录,二叉,return,20,else,root
From: https://www.cnblogs.com/hailicy/p/18318664