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

O1和O2的两种位置情况

O1和O2互为祖先节点

O1和O2不互为祖先节点

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 int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return process(root, o1, o2).val;
    }

    public TreeNode process (TreeNode root, int o1, int o2) {
        // 如果当前节点为空,或者当前节点就是01或02,那就直接返回当前节点
        // 如果一棵树不包含o1或o2,那么它的返回值必然是null,因为叶子节点的返回值就为null
        // 如果o1是o2的祖先节点或者o2是o1的祖先节点,那么从上往下遍历的时候
        // 因为该if条件,必然会直接返回祖先节点
        // 如果o1和o2不是互为祖先节点,那只能是有一个最近的祖先节点
        // 那么对于一棵子树来说,想要有返回值,那么必须得包含o1或者o2,因此该函数的最终返回值为非空的节点
        // 如果一棵子树的左右两个孩子节点所对应的两棵子树的返回值就是o1和o2,那么就直接返回当前节点即可
        // 也就是说: 如果当前节点的左右孩子节点的返回值都不为空,就直接返回当前节点即可
        if (root == null || root.val == o1 || root.val == o2) {
            return root;
        }

        TreeNode left = process(root.left, o1, o2);
        TreeNode right = process(root.right, o1, o2);

        if (left != null && right != null) {
            return root;
        }

        return left != null ? left : right;
    }
}