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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // 转换为找路径
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = new ArrayList<>();
        ArrayList<Integer> path_q = new ArrayList<>();

        getPath(root, o1, path_p);
        getPath(root, o2, path_q);


        int res = 0;
        //比较两个路径，找到第一个不同的点
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if (x == y)
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }
    //求得根节点到目标节点的路径
    public boolean getPath(TreeNode root, int target, ArrayList<Integer> path) {
        // 用回溯来找路径
        if (root == null) return false;
        // 添加
        path.add(root.val);
        // 执行
        if (root.val == target) {
            return true;
        }
        if (getPath(root.left, target, path) || getPath(root.right, target, path)) {
            return true;
        }
        // 回溯
        path.remove(path.size()-1);

        return false;

    }
}