二叉树的最近公共祖先「变题」

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

开头先来一个小插曲，关于「祖先」问题的总结可见 二叉树祖先问题

// 方法一：递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null || right == null) return left == null ? right : left;
    return root;
}

// 方法二：记录父节点，然后找相交点 (同相交链表找交点的方法)
private Map<Integer, TreeNode> parent = new HashMap<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    getParent(root, null);
    TreeNode pp = p, qq = q;
    // 找交点的过程
    while (pp != qq) {
        if (pp == null) pp = q;
        else pp = parent.get(pp.val);
        if (qq == null) qq = p;
        else qq = parent.get(qq.val);
    }
    return pp;
}
// 记录每个节点的父节点
private void getParent(TreeNode root, TreeNode p) {
    if (root == null) return ;
    parent.put(root.val, p);
    getParent(root.left, root);
    getParent(root.right, root);
}

变题一：二叉搜索树的最近公共祖先

题目详情可见 二叉搜索树的最近公共祖先

相比于上面的题目来说更简单，因为二叉搜索树有序！！

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val > q.val) return lowestCommonAncestor(root, q, p);
    if (root == null) return null;
    if (p.val <= root.val && root.val <= q.val) return root;
    if (q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    else return lowestCommonAncestor(root.right, p, q);
}

变题二：最深叶节点的最近公共祖先

题目详情可见 最深叶节点的最近公共祖先

private int[] height = new int[1010];
public TreeNode lcaDeepestLeaves(TreeNode root) {
    getH(root);
    return f(root);
}
private TreeNode f(TreeNode root) {
    if (root == null) return null;
    if (root.left == null && root.right == null) return root;
    if (root.left == null) return f(root.right);
    if (root.right == null) return f(root.left);
    int lh = height[root.left.val];
    int rh = height[root.right.val];
    if (lh == rh) return root;
    else if (lh < rh) return f(root.right);
    else return f(root.left);
}
private int getH(TreeNode root) {
    if (root == null) return 0;
    height[root.val] = Math.max(getH(root.left), getH(root.right)) + 1;
    return height[root.val];
}

变题三：N 叉树的最近公共祖先

建议使用开头给出的方法二，记录父节点！！递归分支太多，不好判断，但也是可以用递归滴！！