【NK四】 在二叉树中找到两个节点的最近公共祖先

根据公共祖先的定义，若root是o1、o2的最近公共祖先，则只可能为以下三种情况之一

1. p 和 q 分别在 root 的左右子树中
2. p = root 且 q 在 root 的 左或右子树中
3. q = root 且 p 在 root 的 左或右子树中

import java.util.*;
public class Solution {

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return CommonAncestor(root, o1, o2).val; 
    }

    public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
    	// 01_如果root为空，或者root为o1、o2中的一个，则它们的最近公共祖先就为root
        if (root == null || root.val == o1 || root.val == o2) { 
            return root;
        }
		// 02_递归遍历左子树，只要在左子树中找到了o1或o2，则先找到谁就返回谁
        TreeNode left = CommonAncestor(root.left,o1,o2);
        // 03_递归遍历右子树，只要在右子树中找到了o1或o2，则先找到谁就返回谁    
        TreeNode right = CommonAncestor(root.right,o1,o2); 
        // 04_如果在左子树中o1和o2都找不到，则o1和o2一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先） 
        if (left == null) { 
            return right;
        }else if (right == null) { // 05_否则，如果left不为空，在左子树中有找到节点（o1或o2），这时候要再判断一下右子树中的情况，如果在右子树中，o1和o2都找不到，则 o1和o2一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
            return left;
        }else{
            return root; // 06_否则，当 left和 right均不为空时，说明 o1、o2节点分别在 root异侧, 最近公共祖先即为 root
        }
    }
}