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

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 {
    public class Info {
        public boolean findP;
        public boolean findQ;
        public int lowestCommonAncestor;

        public Info () {
            this.findP = false;
            this.findQ = false;
            this.lowestCommonAncestor = -1;
        }

        public Info (boolean findP, boolean findQ, int lowestCommonAncestor) {
            this.findP = findP;
            this.findQ = findQ;
            this.lowestCommonAncestor = lowestCommonAncestor;
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here

        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        获知【左子树】中【有无p，q或最小公共祖先】
        //        获知【右子树】中【有无p，q或最小公共祖先】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【有无p，q或最小公共祖先】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      将有无p和q取或；若左右子树已经有lowestCommonAncestor了，则传递，反之则赋值

        // 调用递归函数求解
        return process(root, o1, o2).lowestCommonAncestor;
    }

    public Info process(TreeNode root, int p, int q) {
        // 递归出口
        if (root == null) {
            // 到底返回
            return new Info();
        }

        // 从左右子树获取信息
        Info leftInfo = process(root.left, p, q);
        Info rightInfo = process(root.right, p, q);

        // 根据获取到的信息加工出自己的信息
        // 三者满足其一即可为true
        boolean findP = leftInfo.findP || rightInfo.findP || root.val == p;
        boolean findQ = leftInfo.findQ || rightInfo.findQ || root.val == q;
        if (findP && findQ) {
            // 如果本子树已经同时发现P和Q了
            if (leftInfo.lowestCommonAncestor == -1 && rightInfo.lowestCommonAncestor == -1) {
                // 同时两个子树都不曾同时发现P和Q
                // 说明本结点才是P和Q的最近公共祖先节点
                return new Info(findP, findQ, root.val);
            } else {
                // 同时两个子树中已经有一个找到最近公共祖先节点了
                // 将它们中非-1的那个传递下去
                int val = (leftInfo.lowestCommonAncestor != -1) ? leftInfo.lowestCommonAncestor : rightInfo.lowestCommonAncestor;
                return new Info(findP, findQ, val);
            }
        }
        // 还没同时发现P和Q，将当前状态向上传递
        return new Info(findP, findQ, -1);
    }
}