最近公共祖先

leetcode 美团笔试也考到了就是要找二叉树两个节点的第一个共同的祖先。对于树，没有规定，不一定是一颗二叉查找树。

第一种情况：首先如果这个树是一个二叉树的，并且是一颗二叉查找树的话

由于二叉查找树的左子树节点比父节点小，右子树节点比父节点大，则输入两个节点，只用从根节点开始比较，如果，如果当前节点比这两个节点都大，则最低的公共父节点一定在左子树中，那么遍历左子树节点。如果当前节点比两个节点小，那么遍历右子节点。这样，找到的第一个值在二者之间的节点就是公共的最低的祖先。

代码如下：(在leetcode的ac代码)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if(node1.val>node2.val){
            TreeNode temp = node1;
            node1 = node2;
            node2 =temp;
        }
        if(root==null||root==node1||root==node2) return root;
        if(node1.val<root.val&&node2.val>root.val) return root;
        else if(node1.val<root.val&&node2.val<root.val) return lowestCommonAncestor(root.left,node1, node2);
        else  return lowestCommonAncestor(root.right,node1, node2);
        
        
    }
}

第二种情况：如果只是一般的二叉树，不是搜索树的话可以用递归的方法：方法思路如下：收下看root是否为公共祖先，不是的话，则递归到左右节点（可能效率不怎么好）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right =lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null) return root;
        return left!=null?left:right;
    }
}

第三种如果这个就是一个一般的树亦不一定是二叉树。如何处理？思路就是找出这两个节点的路径，并存在链表中，则这两个链表的交点就是最低公共祖先

实现如下：

    /*-------------------第二种情况--------------------------------------------*/
    //如果这个树只是一个一般的树 也不一定是是二叉树。这里当做二叉树来处理吧。不是二叉树的情况也一样的方法。
    
    public TreeNode fin_nearances3(TreeNode node1,TreeNode node2,TreeNode root){
        if(root==null||node1==root||node2==root) return root;
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        
        
        findpath(root, node1, path1);
        findpath(root,node2,path2);
        return findlastcommonNode(path1, path2);
    }
    //找出节点P的路径 存在path中，如果不存在的话就返回false
    public boolean findpath(TreeNode root,TreeNode p,List<TreeNode> res){
        if(root==p) {
            res.add(root);
            return true;
        }
        
        res.add(root);
        boolean found = false;
        found = findpath(root.left, p, res);
        found = findpath(root.right, p, res);
        if(!found) res.remove(res.size()-1);
        return found;
        
        
    }
    //找出两个path的最后一个公共的节点
    public TreeNode findlastcommonNode(List<TreeNode> path1,List<TreeNode> path2){
        TreeNode res = null;
        int i=0;
        while(i<path1.size()&&i<path2.size()){
            if(path1.get(i)==path2.get(i))
                res = path1.get(i);
            i++;
        }
        
        return res;
    }

//如果只是普通的树不一定是二叉树但是节点中有指向父节点的指针。这样将问题转化为两个链表的第一个交点。

贴一下此博主的解法：

http://blog.csdn.net/xyzbaihaiping/article/details/52122885

最近公共祖先

推荐阅读