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

题目描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
数据范围：树上节点数满足1≤n≤10^5, 节点值val满足区间 [0,n)
要求：时间复杂度O(n)
注：本题保证二叉树中每个节点的val值均不相同。

示例

当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时,二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示:

• 示例1

输入：{3,5,1,6,2,0,8,#,#,7,4},5,1
输出：3

• 示例

输入：{3,5,1,6,2,0,8,#,#,7,4},2,7
输出：2

思路

相信大家看得出这道题和前面的二叉搜索树那道题十分相似
不过这道题却没有像二叉搜索树一样的优势，我们不再能够通过“左小右大”的特点快速收集路径。所以我们只能通过dfs（深度优先搜索）来收集路径。
实现步骤：

• 利用dfs求得根节点到两个目标节点的路径：每次选择二叉树的一颗子树往下找，同时路径数组增加这个遍历的节点值。
• 一旦遍历到了叶子节点也没有，则回溯到父节点，寻找其他路径，回溯时要去掉数组中刚刚加入的元素。
• 然后遍历两条路径数组，依次比较元素值。
• 找到两条路径，第一个相同的节点即是最近公共祖先。

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public boolean flag = false;
    public void getPath(TreeNode root,ArrayList<Integer> path,int o){
        if(root==null){
            return;
        }
        path.add(root.val);
        //节点值都不同,可以直接用值比较
        if(root.val==o){
            flag = true;
            return;
        }
        //dfs查找
        getPath(root.left,path,o);
        getPath(root.right,path,o);
        //找到
        if(flag){
            return;
        }
        //回溯
        path.remove(path.size()-1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        //求根节点到两个节点的路径
        getPath(root,path1,o1);
        //重置flag
        flag = false;
        getPath(root,path2,o2);
        int res = 0;
        for(int i=0;i<path1.size()&&i<path2.size();++i){
            int x = path1.get(i);
            int y = path2.get(i);
            if(x==y){
                res = x;
            }
        }
        return res;
    }
}