二叉树：找出两个节点的最近公共祖先

一、问题描述

给定二叉树(不是二叉搜索树)和两个节点 p 和 q，编程实现找到二者的最近公共祖先(Lowest Common Ancestor，LCA)。

二、思路分析

LCA(Least Common Ancestor)：【最近公共祖先】两个节点所有公共祖先中离根节点最远的节点。从根开始遍历树，如果任意给定节点(p和q)与根匹配，则根为 LCA。如果根与任何节点都不匹配，重复左右子树中寻找节点 p 和 q。如果在其左子树中存在一个节点而在右子树中存在的另一个节点，则此节点即为 LCA。如果两个节点都位于左子树中，则 LCA 也位于左子树中，否则 LCA 位于右子树中。由此，找到该树中两个指定节点的最近公共祖先，有三种情况，如图：

树中从 p 节点到 q 节点的距离：从根到 p 的距离加上从根到 q 的距离，减去从根到它们最近共同祖先的距离的两倍。

三、代码实现

//下面使用的遍历方法为前序遍历
public class Lca {
    // 1、构造二叉树
    public Node buildTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        //这里是构造二叉树的关键
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //找两个结点最近的公共祖先
    public Node lowstCommonAncestor(Node root, Node p, Node q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        Node left = lowstCommonAncestor(root.left, p, q);
        Node right = lowstCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }

    public static void main(String[] args) {
        Lca binaryTree = new Lca();
        Node root = binaryTree.buildTree();
        System.out.println(root);//这个是根即A的地址：com.xxp.common.algorithms.Node@5f4da5c3
        //这里打印出的是地址，可推断该公共祖先是A。与上面比较会发现是一致的
        System.out.println("找两个结点最近的公共祖先：" + binaryTree.lowstCommonAncestor(root, root.left, root.right.left));
        System.out.println(binaryTree.lowstCommonAncestor(root, root.left, root.right.left).val);
        System.out.println(root.val);

    }
}

class Node {
    public char val;
    public Node left;//左孩子
    public Node right;//右孩子

    public Node(char val) {
        this.val = val;
    }
}