给定一颗二叉树，以及其中的两个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)。

    

            
235. Lowest Common Ancestor of a Binary Search Tree





235. Lowest Common Ancestor of a Binary Search Tree


如果大于最大值，则所求在左子树，如果小于最小值，则所求在右子树，否则，返回当前节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    #循环
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if root.val > max(p.val, q.val):
                root = root.left
            elif root.val < min(p.val, q.val):
                root = root.right
            else:
                return root

    #递归
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

    #找路径后比较
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        l1 = self.findPath(root, p)
        l2 = self.findPath(root, q)
        res = root
        for i in range(min(len(l1), len(l2))):
            if l1[i] == l2[I]:
                res = l1[I]
            else:
                break
        return res
    
    def findPath(self, root, p):
        res = []
        while root.val != p.val:
            res.append(root)
            if root.val > p.val:
                root = root.left
            else:
                root = root.right
        res.append(p)
        return res

236. Lowest Common Ancestor of a Binary Tree





236. Lowest Common Ancestor of a Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        mydic = {}
        l1 = self.findPath(root, p)
        l2 = self.findPath(root, q)
        res = root
        for i in range(min(len(l1), len(l2))):
            if l1[i] == l2[I]:
                res = l1[I]
            else:
                break
        return res

    def findPath(self, root, p):
        res = []
        mydic = {}
        qu = [root]
        while qu:
            node = qu.pop(0)
            if node == p:
                break
            else:
                if node.left:
                    qu.append(node.left)
                    mydic[node.left] = node
                if node.right:
                    qu.append(node.right)
                    mydic[node.right] = node
        while node != root:
            res.append(node)
            node = mydic[node]
        res.append(root)
        return res[::-1]


          
  

关于如何求二叉树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);

            }

           }

 }

        

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;
      }
   }
}