题解 | #农场牛群族谱#

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 p int整型
     * @param q int整型
     * @return int整型
     */
    public int result = -1;
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        dfs(root, p, q);

        return result;
    }
    // 自底向上
    public boolean dfs(TreeNode root, int p, int q) {

        // 出口
        if (root == null) {
            return false;
        }

        // 后序遍历（左-右-根）
        boolean leftResult = dfs(root.left, p, q);
        boolean rightResult = dfs(root.right, p, q);

        // 找到了最近的公共祖先（值是唯一的正数）
        // 注：如果找到了最近的祖先节点，后续的遍历，该条件始终是 false；
        // 原因：因为祖先节点的父节点另外的一条分支不可能再次出现 p、q，即另外一半使该条件不会成立
        if ((leftResult && rightResult) || ((leftResult || rightResult) &&
                                            (root.val == p || root.val == q))) {
            result = root.val;
        }

        // 当前子树是否存在 p 或 q 或 同时 存在 p、q
        return leftResult || rightResult || root.val == p || root.val == q;
    }

    // 自顶向下
    // 找到了最近的公共节点后，不会继续递归下去了
    // public int lowestCommonAncestor (TreeNode root, int p, int q) {
    //     // write code here
    //     if (root == null) {
    //         return -1;
    //     }
    //     当前根节点的值 是 p、q 找到一条，或者说 整棵树的根节点是 p、q 直接返回即可(特殊情况)
    //     if (root.val == p || root.val == q) {
    //         return root.val;
    //     }
    //     int leftVal = lowestCommonAncestor(root.left, p, q);
    //     int rightVal = lowestCommonAncestor(root.right, p, q);
    //     左右子树都存在 p 或者 q，找到了
    //     if (leftVal > -1 && rightVal > -1) {
    //         return root.val;
    //     }
    //     return leftVal > -1 ? leftVal : rightVal;
    // }
}