最近公共祖先节点详细解析

寻找最近的公共祖先节点：则只会出现三种情况才返回对当前节点

• 1.当前节点为o1,o2中的一个，且另一个在其左子树中
• 2.当前节点为o1,o2中的一个，且另一个在其右子树中
• 3.当前节点不为o1,o2任一一个，但是o1,o2分别存在于其左右子树中
  那么我们在判断当前节点是否是需要返回的就只需要以下步骤：
  • 1.判断目标节点在左右子树中是否存在
  • 2.根据左右子树返回的情况，判断属于前面三种情况的哪一种
  • 3.如果不是当前节点，则需要判断接下来进入哪一个节点
    具体代码如下

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
        //当前节点分别求出左右子树是否存在目标节点
        boolean left = search(root.left,o1,o2);
        boolean right = search(root.right,o1,o2);
        if(left && right){
            return root.val;
        }else{
            if(root.val == o1 || root.val == o2){
                return root.val;
            }else{
                return left == true ? lowestCommonAncestor(root.left,o1,o2) : lowestCommonAncestor(root.right,o1,o2);
            }
        }
    }

    //定义方法，返回当前节点下，是否存在指定值得节点
    public boolean search(TreeNode root,int target1,int target2){
        if(root == null)return false;
        if(root.val == target1 || root.val == target2)return true;
        return search(root.right,target1,target2) || search(root.left,target1,target2);
    }
}