一、问题描述

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

二、思路分析

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

三、代码实现

import java.util.*;
import java.util.Queue;
//下面使用的遍历方法均为前序遍历
class Node{
    public char val;
    public Node left;//左孩子
    public Node right;//右孩子
    public Node(char val){
        this.val=val;
    }
}
public class BinaryTree {
    // 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) {
        BinaryTree binaryTree=new BinaryTree();
        Node root=binaryTree.buildTree();

        System.out.println("找两个结点最近的公共祖先："+binaryTree.lowstCommonAncestor(root,root.left,root.right.left));//这里打印出的是地址，可推理该公共祖先是A
        System.out.println(root);//这个是根即A的地址，两者比较会发现是一致的
    }
}