本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題68：樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先

題目要求：
輸入一棵樹(shù)的根節(jié)點(diǎn)，輸入兩個(gè)被觀察節(jié)點(diǎn)，求這兩個(gè)節(jié)點(diǎn)的最低(最近)公共祖先。

解題思路：
此題比較開(kāi)放，主要是對(duì)于“樹(shù)”沒(méi)有做明確說(shuō)明，所以原書(shū)中就對(duì)樹(shù)的可能情況做了假設(shè)，然后就衍生出多種思路

1）如果是二叉，搜索樹(shù)：
    遍歷找到比第一個(gè)節(jié)點(diǎn)大，比第二個(gè)節(jié)點(diǎn)小的節(jié)點(diǎn)即可
2）如果是父子間有雙向指針的樹(shù)：
    由下往上看，轉(zhuǎn)化為找兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)問(wèn)題
3）如果只是一個(gè)包含父到子的指針的普通樹(shù)：
   3.1）如果不能使用額外空間，從根節(jié)點(diǎn)開(kāi)始判斷他的子樹(shù)是否包含那兩個(gè)節(jié)點(diǎn)，找到最小的的子樹(shù)即可
        時(shí)間復(fù)雜度o(n^2)(此為最差，平均不太好算。。。),空間復(fù)雜度為o(1)
   3.2) 如果能用額外空間，可以遍歷兩次(深度優(yōu)先)獲取根節(jié)點(diǎn)到那兩個(gè)節(jié)點(diǎn)的路徑，然后求兩個(gè)路徑的最后一個(gè)公共節(jié)點(diǎn)
        時(shí)間復(fù)雜度o(n)，空間復(fù)雜度o(logn)

(1)(2)比較簡(jiǎn)單。下面僅對(duì)(3)，以下圖所示的樹(shù)為例，進(jìn)行思路實(shí)現(xiàn)與求解驗(yàn)證

                        A
                      /   \
                     B     C 
                  /     \
                D        E 
               / \     / | \
              F   G  H   I   J

package chapter7;

import java.util.*;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/22
 * Time  : 17:15
 * Description:樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先
 *
 **/
public class P326CommonParentInTree {
    public static class CommonTreeNode{
        public char val;
        public List<CommonTreeNode> children;
        public CommonTreeNode(char val){
            this.val = val;
            children = new LinkedList<>();
        }
        public void addChildren(CommonTreeNode... children){
            for(CommonTreeNode child:children)
                this.children.add(child);
        }
    }
    // 3.1所述的解法
    public static CommonTreeNode getLastParent1(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
        if(root==null || node1==null || node2==null || !isInSubTree(root,node1,node2))
            return null;
        CommonTreeNode curNode = root;
        while (true){
            for(CommonTreeNode child:curNode.children){
                if(isInSubTree(child,node1,node2)){
                    curNode = child;
                    break;
                }
                if(child==curNode.children.get(curNode.children.size()-1))
                    return curNode;
            }
        }
    }
    public static boolean isInSubTree(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
        Queue<CommonTreeNode> queue = new LinkedList<>();
        CommonTreeNode temp = null;
        int count = 0;
        queue.add(root);
        while (count!=2 && !queue.isEmpty()){
            temp = queue.poll();
            if(temp==node1||temp==node2)
                count++;
            if(!temp.children.isEmpty())
                queue.addAll(temp.children);
        }
        if(count==2)
            return true;
        return false;
    }
    // 3.2所述的解法
    public static CommonTreeNode getLastParent2(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
        List<CommonTreeNode> path1 = new ArrayList<>();
        List<CommonTreeNode> path2 = new ArrayList<>();
        getPath(root,node1,path1);
        getPath(root,node2,path2);
        CommonTreeNode lastParent = null;
        for(int i=0;i<path1.size()&&i<path2.size();i++){
            if(path1.get(i)==path2.get(i))
                lastParent = path1.get(i);
            else
                break;
        }
        return lastParent;
    }
    public static boolean getPath(CommonTreeNode root,CommonTreeNode node,List<CommonTreeNode> curPath){
        if(root==node)
            return true;
        curPath.add(root);
        for(CommonTreeNode child:root.children){
            if(getPath(child,node,curPath))
                return true;
        }
        curPath.remove(curPath.size()-1);
        return false;
    }

    public static void main(String[] args){
        CommonTreeNode root = new CommonTreeNode('A');
        CommonTreeNode b = new CommonTreeNode('B');
        CommonTreeNode c = new CommonTreeNode('C');
        CommonTreeNode d = new CommonTreeNode('D');
        CommonTreeNode e = new CommonTreeNode('E');
        CommonTreeNode f = new CommonTreeNode('F');
        CommonTreeNode g = new CommonTreeNode('G');
        CommonTreeNode h = new CommonTreeNode('H');
        CommonTreeNode i = new CommonTreeNode('I');
        CommonTreeNode j = new CommonTreeNode('J');
        root.addChildren(b,c);
        b.addChildren(d,e);
        d.addChildren(f,g);
        e.addChildren(h,i,j);
        System.out.println(getLastParent1(root,f,h).val);
        System.out.println(getLastParent2(root,f,h).val);
        System.out.println(getLastParent1(root,h,i).val);
        System.out.println(getLastParent2(root,h,i).val);

    }
}

運(yùn)行結(jié)果

B
B
E
E