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

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整型
     */
    /**
     *                                1
     *                          2           3
     *                       4      5     6     7
     *  情况1:
     *  o1或o2 = 1 直接返回根节点
     *  
     *  情况2:
     *  o1 = 2 o2 =3 前序遍历到2时 left = 2 然后前序遍历直接遍历到了3 返回1
     *  
     *  情况3:
     *  o1 = 2 o2 = 5 前序遍历到2停止遍历 left = 2 然后遍历 3 6 7 right = 0 left!=null 返回2
     *  
     *  情况4:
     *  o1 = 4 o2 = 6 前序遍历到4 left = 4 接着遍历5 left=2 right=0 返回2 前序遍历递归返回 当前root=1 接着遍历 3 6 7 left = 6 right = 0 返回6 left right都不为0 返回根节点1
     *  
     *  剩下的情况类似
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {

        /**
         * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2 说明root为非null 并且 o1 o2为树上的节点 不存在o1 o2为莫须有的节点
         * 
         * 前序遍历二叉树,当遍历到叶子节点的时候 即叶子节点的左右子树为null 此时返回0
         */
        if (root == null) {
            return 0;
        }

        //遍历的当前节点与o1或o2 相同时,直接返回其命中的值
        if (root.val == o1 || root.val == o2) {
            return root.val;
        }

        //前序遍历二叉树 此时递归遍历树的左孩子 命中目标后 直接结束遍历 没命中时 继续遍历
        int left = lowestCommonAncestor(root.left, o1, o2);

        //前序遍历二叉树 此时递归遍历树的右孩子
        int right = lowestCommonAncestor(root.right, o1, o2);

        //当左孩子和右孩子 都不为0时,说明此时的root节点为o1 o2的最近公共祖先
        if (left != 0 && right != 0) {
            return root.val;
        }

        //上面的条件 必有left=0 或 right=0 
        if (left != 0) {
            return left;
        }

        if (right != 0) {
            return right;
        }

        //left right都等于0 说明当前整个左子树没有命中O1 O2
        return 0;

    }
}