【解题报告】【lintcode88】Lowest Common Ancestor

题意

解法

代码

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.
     */
  List<List<TreeNode>> lists;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
    TreeNode node = null;
        if (root == null)
            return null;
        lists = new ArrayList<List<TreeNode>>();
        List<TreeNode> a = new ArrayList<>();
        List<TreeNode> b = new ArrayList<>();
        findNode(root,a,A);
        findNode(root,b,B);//寻找路径
        a = lists.get(0);
        b = lists.get(1);
          int la = a.size();
        int lb = b.size();
        int i = 0,j=0;
        //开始比较路径
        while ( i<la && j<lb){
            if (a.get(i).val != b.get(j).val) {
                node = a.get(i-1);
                break;
            }
           i++;
            j++;
        }
        if (i >= la||j >= lb){
            return a.get(i-1);
        }
        return node;
    }
 private void findNode(TreeNode node, List<TreeNode> list,TreeNode target){
 
        if (node == null)
         return;
        if (node.val == target.val){
            list.add(node);
            lists.add(list);
            return;
        }
       List<TreeNode> list1 = new ArrayList<>();
       list1.addAll(list);
       list1.add(node);
        findNode(node.left,list1,target);
        findNode(node.right,list1,target);
    }
}