给定一颗二叉树，以及其中的两个node（地址均非空），要求给出这两个node的一个公共父节点，使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度，并实现具体函数，函数输入输出请参考如下的函数原型：

 
C++函数原型：

 
 
 
 
  
strucy TreeNode{
     TreeNode* left;   //指向左子树
     TreeNode* right;   //指向右子树
     TreeNode* father;   //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}
  
 
  
 
   
  
 
   思路一：我们首先找到两个节点的高度差，然后从较靠近根结点的一层开始向上找，若父节点为同一节点则该节点为解。
  
 
  
 
   
intgetHeight(TreeNode *node) {
    intheight = 0;
    while(node) {
        height++;
        node = node->parent;
    }
    returnheight;
}
 
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
    intheight1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
    if(diff < 0) {
        diff = -diff;
        while(diff--) {
             second = second->parent;
        }
    } else{
        while(diff--) {
            first = first->parent;
        }
    }
    while(first != second) {
        first = first->parent;
        second = second->parent;
    }
    returnfirst;
}

   
 
  
 
  
 
  
 
  
 
   思路二：若允许浪费空间，那么可以用两个Stack来存储从first和second到根结点的各个节点，然后出栈时比较地址是否一致，最后一个地址一致的节点为解。
  
 
  
 
   
 
  
 
  

    两种方法最坏时间复杂度均为O(n)。
  
 
  
 
 
 

有一个普通二叉树，AB分别为两个子节点，求AB最近（深度最大）的公共父节点。 
 此题仍然是一个老题，有着多种解决方法，本文针对其中三种方法来进行分析总结。
 
这三种方法分别是：递归法，tarjan离线算法，RMQ在线算法。
 
 
递归法
 
递归法比较直观简单，思路如下：
 
首先判定当前节点root是否是A节点或者B节点，若是的话直接返回该节点
若不是，分别对root节点的左右子树进行递归查找最小公共父节点，若左右子树都返回了节点，那么表示当前节点就是最小公共父节点，若只有其中一个子树返回了结果，那么就返回该结果节点。
 
参考代码如下：
 
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            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) return right;
        if(right==NULL) return left;

        return root;
    }
 
 
 如上图中我们要查找节点4,3的最小公共父节点，那么上述代码的执行过程如下
 
判断1是否4,3节点不是，查询1的左子树和右子树
1的左子树中先判断2是否4,3节点不是，查找2的左右子树 
 
  
2的左子树 显然返回结果4，2的右子树返回结果NULL，显然2的左右子树并没有都返回树中的节点，因此2不是4,3的最小公共父节点，因此以2位根节点的1的左子树调用方法返回的是4.
1的右子树判断3节点是否是4,3节点，发现是的，直接返回3节点。
1的左右子树的递归调用都返回了结果，因此1就是节点4,3的最小公共父节点。 
 
 
Tarjan离线算法
 
对于该算法，常常会有一个给定的树T和一个给定的查询集合P={（u，v）}，我们需要确定P中每对的最小公共祖先。 
 算法为何说是离线的？因为针对所有的查询，我们都是在算法的一次执行过程中找到。
 
算法思路：
 
根节点root开始搜索，每次递归搜索所有的子树
当搜索到节点u时，创建一个由u本身组成的集合，这个集合的祖先为u自己。然后递归搜索u的所有儿子节点。每个儿子节点递归完毕之后，将儿子节点所在的集合和u所在的集合合并，再把该集合的祖先设定为节点u。
每个节点的所有孩子都递归完毕后，将该节点设定为已经访问过，开始遍历所有u的查询，若发现查询的另外一个节点v也是标示为访问过的话，那么节点u和v的最小公共父节点即为节点v所在集合的祖先节点。
 
上述所有操作都是使用并查集高效完成的。因此时间复杂度，O(n)深度优先搜索所有节点的时间，搜索每个节点时会遍历这个节点相关的所有查询。如果总的查询个数为q，则总的复杂度为O(n+q)。
 
还是上图的树，我们从节点1开始，创建集合{1}，然后递归到1的第一个孩子节点2，创建集合{2}，之后继续深度递归到节点4，创建集合{4}，完成节点4的访问后，将4设定为已访问，集合{4}与集合{2}合并，得到{4,2}，将他们的祖先设为2，然后访问节点5，创建集合{5}，完成之后将集合{2,4}和{5}合并，得到{2,4,5}然后将该集合的祖先设为2，若此时（5,4）是一个查询，那么就可以得到他们的最小公共祖先为2。之后合并{1}和{2,4,5}得到{1,2,4,5},祖先为1，访问3，继续访问6，完成之后，若(6,2)是一个查询，那么其最小公共祖先为1。剩下的操作类似。
 
伪代码如下（参考算法导论）：
 
LCA(u)
  MAKE-SET(u)
  Find-Set(u).ancestor = u
  for each child v of u in T
      LCA(u)
      Union(u,v)
      Find-Set(u).ancestor = v
  u.color= Black
  for each node v such that (u,v) belongs to P
            if v.color ==Black
               print "The LCA of "u "and" v"is" Find-Set(v).ancestor
 
 
RMQ在线算法
 
无论是一个询问还是很多个询问，使用离线算法都是只需要做一次深度优先搜索就可以了的。所以离线算法针对一次性较多查询的话比较实惠，但是每次只来一个查询，这时候多次调用离线算法就不值当了。在线算法处理这种情况比较合适。
 
之前文章里写过RMQ在线算法的原理了，这里就不加多说，本文主要介绍如何把RMQ算法和最小公共父节点问题结合起来。
 
算法思路：
 
LCA集合RMQ主要是通过DFS（深度优先搜索）完成。每次经过某一个点——无论是从它的父亲节点进入这个点，还是从它的儿子节点返回这个点，都按顺序记录下来，还是上面的树，DFS之后顺序为：1-2-4-2-5-2-1-3-6-3-1。那么要找到树上两个节点的最近公共祖先，无非就是找到这两个节点最后一次出现在数组中的位置所囊括的一段区间中深度最小的那个点，并且我们假定我们的树中每个父亲节点的标号都比孩子节点小，那么目标就转换为求该区间中标号最小的那个节点。
 
部分代码如下：
 
int ind[N];//用来存储每个节点在生成路径中最后一次出现的位置
vector<int> road;//存储DFS路径
void dfs(int s)
{
    road.push_back(s);
    for(int i = 0; i < V[s].size();i++){
        dfs(V[s][i]);
        road.push_back(s);
    }
}
 
得到路径之后，那么每个节点在生成路径中最后一次出现的位置可以用如下方式得到：
 
for(int i = 0; i < road.size();i++)
{
        ind[road[i]] = i + 1;
}
 
进行上述操作之后，对于每一对查询(u,v)，我们再利用RMQ区间查询的算法输入ind[u],ind[v]就能得到其最小公共父节点了。
 
 
总结
 
本文总结了三种不同求解最小公共父节点的方法，本人曾在微软面试中被问及此题，答得并不是很好，若是能在面试中答出多种方法，那么一定会有大大的加分。

package com.Tree;
 
 
 
import java.util.LinkedList;
 
 
 
public class CommonFather {
 
 
 
  /**
 
   * 题目描述：给定一棵二叉树，要求找到其中任意两节点的最小公共父节点。
 
   * 思路:最原始的方法，从根开始，分别寻找从根节点到每个目标节点的路径，然后比较 两条路径，找到最小的公共父节点。
 
   * @param args
 
   * @author Adai
 
   */
 
  private LinkedList<TNode> path;
 
  private static class TNode{
 
     int data;
 
      TNode leftchild;
 
      TNode rightchild;
 
     public TNode(int da){
 
        this.data=da;
 
        this.leftchild=null;
 
        this.rightchild=null;
 
      }
 
   }
 
  private TNode root;
 
  public CommonFather(int[] list){
 
      TNode curr=null;
 
     for(int i=0;i<list.length;i++){
 
         TNode now=new TNode(list[i]);
 
        if(i==0){
 
           root=now;
 
            curr=root;
 
         }else{
 
            curr=root;
 
           while(curr!=null){
 
               if(curr.data<now.data){
 
                  if(curr.rightchild!=null){
 
                      curr=curr.rightchild;
 
                   }else{
 
                      curr.rightchild=now;
 
                     break;
 
                   }
 
                }else{
 
                  if(curr.leftchild!=null){
 
                      curr=curr.leftchild;
 
                   }else{
 
                      curr.leftchild=now;
 
                     break;
 
                   }
 
                  
 
                }
 
            }
 
           
 
         }
 
      }
 
   }
 
  public static void main(String[] args) {
 
     // TODO Auto-generated method stub
 
     int[] list={5,4,6,3,7,2,8,1,9};
 
      CommonFather cf=new CommonFather(list);
 
      TNode tar=cf.FindCommonFather(cf.root, 3, 7);
 
      System.out.println(tar.data);
 
   }
 
  public TNode FindCommonFather(TNode root,int t1,int t2){
 
     if(root==null) return null;
 
     path=new LinkedList<TNode>();
 
      LinkedList<TNode> set=new LinkedList<TNode>();
 
      TNode cur=root;
 
     if(FindTNode(cur,t1)){
 
        
 
        while(!path.isEmpty()){
 
            TNode now=path.pop();
 
            set.push(now); 
 
            System.out.println(now.data);
 
         }
 
      }else{
 
        return null;
 
      }
 
     path.clear();
 
      cur=root;
 
      LinkedList<TNode> guest=new LinkedList<TNode>();
 
     if(FindTNode(cur,t2)){
 
         TNode cf=null;
 
        while(!path.isEmpty()){
 
            TNode now=path.pop();
 
            System.out.println("2:"+now.data);
 
            guest.push(now);
 
         }
 
      }else{
 
        return null;
 
      }
 
      TNode ret=null;
 
     while(!set.isEmpty()&&!guest.isEmpty()){
 
         TNode se=set.pop();
 
         TNode ge=guest.pop();
 
        if(se.equals(ge)){
 
            ret=se;
 
         }else{
 
           return ret;
 
         }
 
      }
 
     return null;
 
   }
 
  
 
  private boolean FindTNode(TNode nowroot,int target){
 
     path.push(nowroot);
 
     if(nowroot==null){
 
        path.pop();
 
        return false;
 
      }else if(nowroot.data==target){
 
        return true;
 
      }else{
 
        if(FindTNode(nowroot.leftchild,target)){
 
           return true;
 
         }
 
        if(FindTNode(nowroot.rightchild,target)){
 
           return true;
 
         }
 
        path.pop();
 
        return false;
 
      }
 
   }
 
}

关于如何求二叉树2个节点的最小公共父节点，分2种情况讨论
 
情况1：节点有parent节点
 
           这种情况就直接找到节点1和节点2的根节点，然后求得2个链表的长度，再求得长度差。如果说2条链子的长度差为n，那么
 
 就长的节点先移动n步，然后和短的节点一起移动，并且判断父节点是否相等。那么这边其实也解决了另一个问题，就是求2个链表
 
 的交点。
 
 
            public static Node publicNode(Node node1,Node node2){
 
            //接下来是求2个条链的起始点
 
            int length1 = getLength(node1);
 
 
            int length2 = getLength(node2);
 
           Node firstNode,secondNode;
 
 
            int res = 0;
 
 
            if(length1>=length2)
 
            res = length1 - length2;
 
            for(int i = 0;i<res;i++){
 
            firstNode = firstNode.parent;
 
 
            }
 
 
            else{
 
            res = length2 - length1;
 
            for(int i = 0;i<res;i++){
 
            secondNode = secondNode.parent;
 
 
            }
 
          // 接下来是从起始节点开始找交点
 
 
           while(firstNode.parent!=null||secondNode.parent!=null){
 
                      if(node1.parent==node2.parent)
 
                      return node1.parent;
 
                      else{
 
                         firstNode = firstNode.parent;
 
                         secondNode = secondNode.parent;
 
 
                      }
 
 
           }
 
           }
 
       其实会这么一个问题，就会求链表的交点和求二叉树的2个节点的最小公共父节点了。
 
  情况2，节点没有parent节点
 
  这个其实也简单，就是从根节点开始层次遍历这棵树，然后判断当前节点是否包含2个节点，如果包含就继续遍历当前节点的
 
  左右节点是否包含这2个节点，如果包含就继续深入。如果左右都不包含，那么当前节点就是最小公共父节点。
 
  public static Node getPublicNode(Node node1,Node node2){
 
            //获得根节点,并且对根节点进行层次遍历
 
 
            Node root = getRoot(node1);
 
            Deque<Node> deque = new Deque<Node>();
 
            deque.add(root);
 
            while(deque.size()!=0){
 
            Node node = deque.peekFirst();
 
            if(node.containChilds(node1,node2)){
 
             //当当前节点包含2个节点，而它的左右节点都不包含2个节点，那么它就是最小公共父节点
 
 
            if(node.left!=null&&node.right!=null&&!node.right.containChilds&&!node.left.containChilds){
 
             return node;
 
 
             }
 
 
            if(node.left!=null&&node.left.containChilds(node1,node2))
 
            deque.add(node.left);
 
           if(node.right!=null&&node.right.containChilds(node1,node2))
 
            deque.add(node.right);
 
 
            }
 
 
           }
 
 
 }