面试题68(剑指offer)--树中两个节点的最低公共祖先

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最低公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

输入: 
root = [4,2,1,3,5,7], p = 3, q = 1
输出: 2
解释: 节点 3 和节点 1 的最近公共祖先是节点 2。

思路：

利用递归遍历找到分别到两个目标点的路径，然后遍历两个路径，两个路径中最后一个相等的元素就是最低的公共祖先。

代码：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==p||root==q||root==null){
            return root;
        }
        List<TreeNode> list=new ArrayList<>();
        List<TreeNode> resList=new ArrayList<>();//存根节点到目标点的路径
        preOrder(root,p,list,resList);
        int pLen=resList.size();
        List<TreeNode> pList=new ArrayList<>();
        for (int i = 0; i < pLen; i++) {
            pList.add(resList.get(i));
        }
        resList.clear();
        list.clear();
        preOrder(root,q,list,resList);
        int qLen=resList.size();
        TreeNode resNode=null;
        for (int i = 0; i < qLen; i++) {
            if (i<pList.size()&&pList.get(i)==resList.get(i)){
                resNode=pList.get(i);//找到最后一个相等的点
                continue;
            }else {
                break;
            }
        }
        return resNode;
    }
    private void preOrder(TreeNode root,TreeNode target,List<TreeNode> list,List<TreeNode> resList){
        if (root==null){
            return;
        }
        list.add(root);
        if (root==target){
            for (TreeNode treeNode : list) {
                resList.add(treeNode);
            }
            return;
        }
        preOrder(root.left,target,list,resList);
        preOrder(root.right,target,list,resList);
        list.remove(root);
    }