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

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

        // List<Integer> nodeList1 = new ArrayList<>();
        // findFather(root, o1, nodeList1);

        // isFind = false;
        // List<Integer> nodeList2 = new ArrayList<>();
        // findFather(root, o2, nodeList2);

        // int result = 0;
        // for (int i = 0; i < nodeList1.size() && i < nodeList2.size(); i++) {
        //     if (nodeList1.get(i) == nodeList2.get(i)) {
        //         result = nodeList1.get(i);
        //     }else{
        //         break;
        //     }
        // }

        // return result;

        if(root == null) return -1;
        if(root.val == o1 || root.val == o2) return root.val;

        int left = lowestCommonAncestor (root.left, o1, o2);
        int right = lowestCommonAncestor (root.right, o1, o2);

        if(left == -1) return right;
        if(right == -1) return left;

        return root.val;
    }

    private boolean isFind = false;
    private void findFather(TreeNode root, int target, List<Integer> paths) {

        if (isFind || root == null) return;

        paths.add(root.val);

        if (root.val == target) {
            isFind = true;
            return;
        }

        findFather(root.left, target, paths);
        findFather(root.right, target, paths);

        if(isFind) return; //找到元素

        paths.remove(paths.size()-1);//回溯
    }

}