參考文章： http://blog.csdn.net/bh_xiaoxinba/article/details/53030043

題目

給定一顆二叉樹的頭結(jié)點，和這顆二叉樹中2個節(jié)點n1和n2，求這兩個節(jié)點的最近公共祖先；

思路

利用后序遍歷實現(xiàn)；
對于當前節(jié)點cur，如果節(jié)點為null或者等于n1或n2中的一個，則直接返回cur；
先處理左右子樹，左子樹返回left，右子樹返回right；判斷l(xiāng)eft和right；
1）left和right均為null，說明以cur為根的樹上沒發(fā)現(xiàn)n1和n2；
2）left和right均不為null，說明在左子樹上發(fā)現(xiàn)了n1或n2，在右子樹上也發(fā)現(xiàn)了n1或n2，cur為n1和n2的首次相遇節(jié)點，則直接返回cur；
3）left和right中一個null，另一個不為null，說明不為空的節(jié)點是n1和n2的其中一個，或者是n1和n2的最近公共祖先；則返回不為空的節(jié)點；

代碼

public class LowestAncestor {

    /*求解n1和n1的最近公共祖先
     * 
     * 利用后序遍歷求解
     */
    public Node getLowestAncestor(Node head,Node n1,Node n2){
        if(head==null || head==n1 || head==n2){
            return head;
        }

        //先遍歷左右子樹，左右子樹的返回為left和right；然后判斷l(xiāng)eft和right請情況
        Node left=getLowestAncestor(head.left,n1,n2);
        Node right=getLowestAncestor(head.right,n1,n2);


        /*左和右都不為null---說明在左子樹中發(fā)現(xiàn)過n1或n2，
         * 在右子樹上也發(fā)現(xiàn)過n1或n2，并且n1和n2在當前節(jié)點首次相遇
         */
        if(left!=null && right!=null){
            return head;
        }

        /*左和右中一個不為null，另一個為null，
         * 說明不為null的節(jié)點是n1或n2中的一個，或者是n1和n2的最近祖先；
         * 直接返回；
         */
        if(left!=null){
            return left;
        }
        if(right!=null){
            return right;
        }

        //左和右均為null，沒有發(fā)現(xiàn)n1和n2；
        return null;
    }

}

遞歸理解

今天剛看到這個題目的遞歸解法時，感覺很繞，覺得方法很好，可就是想不清楚遞歸遍歷到樹的更深層級的返回值應該是什么。實在沒辦法理解，拿筆畫了畫，終于get到點了，就有了下一小結(jié)的遞歸執(zhí)行過程圖。

實例分析

遞歸執(zhí)行過程舉例.png