lintcode :最近公共祖先

题目

最近公共祖先

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

样例

对于下面这棵二叉树

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

解题

不知道如何下手，参考链接，自顶向下的解法中有下面的说明：

初首先看看3和5，这两个节点分居根节点4的两侧，如果可以从子节点往父 节点递推，那么他们将在根节点4处第一次重合；再来看看5和6，这两个都在根节点4的右侧，沿着父节点往上递推，他们将在节点7处第一次重合；最 后来看看6和7，此时由于7是6的父节点，故7即为所求。从这三个基本例子我们可以总结出两种思路——自顶向下(从前往后递推)和自底向上(从后 往前递推)。

顺着上述实例的分析，我们首先看看自底向上的思路，自底向上的实现用一句话来总结就是——如果遍历到的当前节点是 A/B 中的任意一个，那么我们就向父节点汇报此节点，否则递归到节点为空时返回空值。具体来说会有如下几种情况：

1.当前节点不是两个节点中的任意一个，此时应判断左右子树的返回结果。
　　1.若左右子树均返回非空节点，那么当前节点一定是所求的根节点，将当前节点逐层向前汇报。// 两个节点分居树的两侧
　　2.若左右子树仅有一个子树返回非空节点，则将此非空节点向父节点汇报。// 节点仅存在于树的一侧
　　3.若左右子树均返回NULL, 则向父节点返回NULL. // 节点不在这棵树中
2.当前节点即为两个节点中的一个，此时向父节点返回当前节点

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if( root ==null || A==root || B == root)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,A,B);
        TreeNode right = lowestCommonAncestor(root.right,A,B);
        if(left != null && right !=null)
            return root;
        if(left!=null)
            return left;
        return right;
    }
}

Java Code

Python

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
import copy
class Solution:
    """
    @param root: The root of the binary search tree.
    @param A and B: two nodes in a Binary.
    @return: Return the least common ancestor(LCA) of the two nodes.
    """ 
    def lowestCommonAncestor(self, root, A, B):
        # write your code here
        if root == None or root == A or root == B:
            return root
        left = self.lowestCommonAncestor(root.left,A,B)
        right = self.lowestCommonAncestor(root.right,A,B)
        if left!=None and right!=None:
            return root
        if left!=None:
            return left
        return right

Python Code

这个博客给了dfs的解法，但是用java一直写不对，在LeetCode discuss 找到了根据DFS从根节点找到当前节点的路径，知道路径就很简单了，这里还是看程序吧

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if( root ==null || A==root || B == root)
            return root;
        ArrayList<TreeNode> pathA = new ArrayList<TreeNode>();
        ArrayList<TreeNode> pathB = new ArrayList<TreeNode>();
        dfs(root,pathA,A);
        dfs(root,pathB,B);
        TreeNode res = null;
        for(int i=0;i<Math.min(pathA.size(),pathB.size());i++){
            TreeNode pa = pathA.get(i);
            TreeNode pb = pathB.get(i);
            if(pa == pb){
                res = pa;
            }else{
                break;
            }
        }
        return res;
    }
    public boolean dfs(TreeNode root,ArrayList<TreeNode> path,TreeNode node){
        if(root == null)
            return false;
        if(node == root){
            // 最后一个节点也要加进去，不然会出错
            path.add(root);
            return true;
        }
        path.add(root);
        if(dfs(root.left,path,node) ==true)
            return true;
        if(dfs(root.right,path,node) ==true)
            return true;
        path.remove(path.size() -1);
        return false;
    }
}