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

递归yyds

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) {
    return helper(root, o1, o2).val;
}
 
public TreeNode helper(TreeNode root, int o1, int o2) {
    if (root == null || root.val == o1 || root.val == o2)
        return root;
    TreeNode left = helper(root.left, o1, o2);
    TreeNode right = helper(root.right, o1, o2);
    //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
    if (left == null)
        return right;
    //同上
    if (right == null)
        return left;
    //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回cur结点即可。
    return root;
}
}