在二叉树中找到最近公共祖先

先来分析：考察的数据结构是二叉树，考察的算法是二叉树的深度遍历。假设当前节点A，A到o1,o2的距离最小的条件限制有
1 A 均能到o1,o2
2 A 到 o1，o2 的路程和最小
所以思路变成先遍历外面的大树，通过遍历然后针对每一个节点进行可达性以及路程的计算，迭代更新路程最小的节点，其实对于树的遍历，相当于是我们在做 for 循环，然后针对循环到的每一个元素，再进行深入的探查，这是二叉树这类题的常用手段，那么如何进行探查尼？还是dfs.所以一般二叉树都要用两个“循环”，一次是以最顶上的根节点为开始的“循环”，一次是以大循环遍历到的点，再以这个点为根节点进行循环的子循环。

TreeNode[] res,int [] dp 用了两个对象来记录中间结果，作用域比较广，比较方便。

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    // write code here
    if(root==null){
        return -1;
    }
    TreeNode [] res=new TreeNode[1];
    int [] dp=new int [1];
    preOrder(root,o1,o2,res,dp);
    return res[0].val; 
}

//大循环 dfs,遍历整棵大树
public void preOrder(TreeNode root,int o1,int o2,TreeNode[] res,int [] dp){
    if(root==null){
        return ;
    }
    int step1=getSteps(root,o1,0);
    int step2=getSteps(root,o2,0);
    if(step1!=-1 && step2!=-1){//排除不可达的点，这里有剪枝优化，因为如果根都不可达，左右子树一定是不可达的，因此只下探这种情况
        int steps=step1+step2;
        if(dp[0]!=0){
            if(dp[0]>steps){//迭代更新
                dp[0]=steps;
                res[0]=root;
            }
        }else{//初始化
            dp[0]=steps;
            res[0]=root;
        }
        preOrder(root.left,o1,o2,res,dp);
        preOrder(root.right,o1,o2,res,dp);
    }
}

//以大树的每一个节点为根节点进行 dfs ，开始子循环遍历
public int getSteps(TreeNode root,int o1,int step){
    if(root!=null){
        if(root.val==o1){//找到了目标值了，返回 step 路程数
            return step;
        }else{
            return Math.max(getSteps(root.left,o1,step+1),getSteps(root.right,o1,step+1)); //继续向下循环，但一定是左右子树最大的路径。主要是和 -1 比较
        }
    }else{
        return -1; //遍历到了空节点，说明不可达，路程为-1
    }
}