BM38 题解 | #在二叉树中找到两个节点的最近公共祖先#

心路历程：

1、在做这道题的过程中，慢慢对二叉树的递归和回溯，算是有了更加深入的理解，极简数据的调试，找到了递归回溯过程中，

增加isFound的的作用所在，没有加时，会有什么影响等等，都在代码里面注释清楚了。

2、另一个注意点，就是记录递归回溯的路径的数据结构不要用LinkedList，会导致超时异常，我换上ArrayList就好了，这个是要注意的！

解题思路：

1、使用前序遍历二叉树，找到对应的path；

2、再通过for循环找出path里面的公共节点就可以了。

import java.util.*;


public class Solution {
    boolean isFound = false;
    /**
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();
        isFound = false;
        dfs(root, o1, path1);
        isFound = false;
        dfs(root, o2, path2);

        int res = 0;
        for(int i=0; i<path1.size() && i<path2.size(); i++){
            int i1 = path1.get(i);
            int i2 = path2.get(i);
            if(i1==i2) {
                res = i1;
            } else {
                break;
            }
        }

        return res;
    }

    /**
     * 这里我发现用LinkedList记录path会有异常，算法跑不过
     * 要用ArrayList，有可能大数据的时候，LinkedList消耗的空间，
     * 或者链接到了别到地方导致异常了
     */
    public void dfs(TreeNode root, int target, ArrayList<Integer> path) {
        if(root == null) {
            return;
        }
        //这里进来的时候，也要判断是否已经找到了，
        //不然又会加入新的未被递归遍历过的值
        if(isFound) {
            return;  
        }
        // visit T
        path.add(root.val);
        if(root.val  == target) {
            isFound = true;
            return;
        }

        dfs(root.left, target, path);
        dfs(root.right, target, path);

        // 这里递归回溯回父节点的时候，判断isFound，
        // 不判断，即使找到了，还是会被一个个删除
        if(isFound) {
            return;
        }
        path.remove(path.size()-1);
    }
}