力扣labuladong一刷day39天最近公共祖先问题

力扣labuladong一刷day39天最近公共祖先问题

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
思路：寻找最近公共祖先，在前序的位置判断，如果找到一个就返回，然后在后序的位置收尾，即左右子树都遍历过了，如果都找到的话当前节点即为最近公共祖先。前序和后序各能解决一种情况，即以其中一个为根节点，另一个是其子树里的，另一个就是两个都是子树。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val == p.val || root.val == q.val) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) return root;
        
        return left != null ? left : right;
    }
}

二、二叉树的最近公共祖先 IV

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iv/
思路：和上一题类似，不过就是节点多一些，放在set里面判断即可。

class Solution {
    Set<Integer> set;
    TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        set = new HashSet<>(nodes.length);
        for (TreeNode node : nodes) {
            set.add(node.val);
        }
        return findAncestor(root);
    }

    TreeNode findAncestor(TreeNode root) {
        if (root == null) return null;
        if (set.contains(root.val)) return root;
        TreeNode left = findAncestor(root.left);
        TreeNode right = findAncestor(root.right);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii/
思路：本题是一个变种，即p和q都在树里才返回公共祖先，p和q只有一个在树里的返回null，也就是p和q不一定在树里，这个时候就不能在前序遍历的位置返回，这样就不会去遍历子树，无法确保另一个也在，现在就必须得每个节点都遍历，在后序的位置判断返回，并且设置全局变量。

class Solution {
    TreeNode nodeP = null, nodeQ = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        TreeNode node = findAncestor(root, p, q);
        if (node != null && nodeP != null && nodeQ != null) {
            return node;
        }
        return null;
    }

    TreeNode findAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        TreeNode left = findAncestor(root.left, p, q);
        TreeNode right = findAncestor(root.right, p, q);
        if (root.val == p.val) {
            nodeP = root;
            return root;
        }
        if (root.val == q.val) {
            nodeQ = root;
            return root;
        }
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
思路：对于二叉搜索树寻找最近公共祖先要利用二叉搜索树的特性，如果有公共祖先的话，最近的一定是min <= node.val <= max的，不在范围内，大于最大值去left寻找，小于最小值去right寻找，剩下的即为答案，直接返回。

class Solution {
   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int min = Math.min(p.val, q.val);
        int max = Math.max(p.val, q.val);
        return find(root, min, max);
    }

    TreeNode find(TreeNode root, int min, int max) {
        if (root == null) return null;
        if (root.val > max) return find(root.left, min, max);
        if (root.val < min) return find(root.right, min, max);
        return root;
    }
}

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iii/
思路：二叉树寻找最近的公共祖先，只给两个节点，就是和寻找两个链表是否相交，找相交的最近的节点。

class Solution {
     public Node lowestCommonAncestor(Node p, Node q) {
        int lenP = 0, lenQ = 0;
        Node a = p, b = q;
        while (a != null) {
            a = a.parent;
            lenP++;
        }
        while (b != null) {
            b = b.parent;
            lenQ++;
        }
        a = p;
        b = q;
        for (int i = lenP; i < lenQ; i++) {
            b = b.parent;
        }
        for (int i = lenQ; i < lenP; i++) {
            a = a.parent;
        }
        while (a != null && a != b) {
            a = a.parent;
            b = b.parent;
        }
        return a;
    }
}