力扣labuladong——一刷day41

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

如果说笔试的时候经常遇到各种动归回溯这类稍有难度的题目，那么面试会倾向于一些比较经典的问题，难度不算大，而且也比较实用。 本文就用 Git 引出一个经典的算法问题：最近公共祖先（Lowest Common Ancestor，简称 LCA）。 git pull 这个命令我们经常会用，它默认是使用 merge 方式将远端别人的修改拉到本地；如果带上参数 git pull -r，就会使用 rebase 的方式将远端修改拉到本地。 这二者最直观的区别就是：merge 方式合并的分支会看到很多「分叉」，而 rebase 方式合并的分支就是一条直线。但无论哪种方式，如果存在冲突，Git 都会检测出来并让你手动解决冲突。 那么问题来了，Git 是如何检测两条分支是否存在冲突的呢？

一、力扣236. 二叉树的最近公共祖先

/**
 * 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) {
        return fun(root,p.val,q.val);
    }
    public TreeNode fun(TreeNode root ,int val1, int val2){
        if(root == null){
            return null;
        }
        if(root.val == val1 || root.val == val2){
            return root;
        }
        TreeNode lchild = fun(root.left, val1, val2);
        TreeNode rchild = fun(root.right, val1, val2);
        if(lchild != null && rchild != null){
            return root;
        }
        return lchild != null ? lchild : rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二、力扣1676. 二叉树的最近公共祖先 IV

/**
 * 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[] nodes) {
        if(root == null){
            return null;
        }
        for(TreeNode n : nodes){
            if(root == n){
                return root;
            }
        }
        TreeNode lchild = lowestCommonAncestor(root.left,nodes);
        TreeNode rchild = lowestCommonAncestor(root.right,nodes);
        if(lchild != null && rchild != null){
            return root;
        }
        return lchild != null ? lchild : rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

三、力扣1644. 二叉树的最近公共祖先 II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flagL = false, flagR = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = fun(root,p,q);
        if(flagL && flagR){
            return res;
        }
        return null;
    }
    public TreeNode fun(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }
        TreeNode lchild = fun(root.left,p,q);
        TreeNode rchild = fun(root.right, p, q);
        if(lchild != null && rchild != null){
            return root;
        }
        if(root == p || root == q){
            if(root == p){
                flagL = true;
                return root;
            }
            if(root == q){
                flagR = true;
                return root;
            }
        }
        return lchild != null ? lchild : rchild; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

四、力扣235. 二叉搜索树的最近公共祖先

/**
 * 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) {
        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left,p,q);
        }else if(root.val < p.val &&root.val < q.val){
            return lowestCommonAncestor(root.right,p,q);
        }else{
            return root;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、力扣1650. 二叉树的最近公共祖先 III

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        while(fun(p,q) == null){
            p = p.parent;
        }
        return p;
    }
    public Node fun(Node p, Node q){
        if(p == null){
            return null;
        }
        if(p == q){
            return p;
        }
        Node l = fun(p.left,q);
        Node r = fun(p.right,q);
        if(l != null){
            return l;
        }
        if(r != null){
            return r;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

链表寻找共同节点操作

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while(a != b){
            if(a == null) a = q;
            else a = a.parent;
            if(b == null) b = p;
            else b = b.parent;
        }
        return a;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22