题解 | #二叉搜索树的最近公共祖先#

最近公共祖先的特征

1:自身就是候选节点

2：两个候选值分别在其左右子树中，这边通过一个findNode的计数函数来判断两个节点的分布情况，然后缩减问题规模

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        //先找一个，再找一个？
        //归纳法的思维
        TreeNode ptr = root;
        int count = 0;
        //本身就是两个候选值里面的一个，自己就是公共父节点
        //若一个节点在左子树，一个节点在右子树
        while(ptr!=null){
            if(ptr.val==p ||ptr.val==q){
                return ptr.val;
            }else{
                //查找匹配节点的总数，先找左子树
                count = findNode(ptr.left,p,q);
                //1.p,q均在左子树
                if(count==2){
                    ptr=ptr.left;
                //2.其中一个在左子树
                }else if(count==1){
                    return ptr.val;
                //3.必在右子树
                }else{
                    ptr=ptr.right;
                }
            }
        }
        return -1;
    }
    public int findNode(TreeNode root, int p, int q){
        int count = 0;
        if(root==null){
            return 0;
        }
        if(root.val==p || root.val==q){
            count++;
        }
        count+=findNode(root.left,p,q);
        count+=findNode(root.right,p,q);
        return count;
    }
}