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

import java.util.*; public class Solution { int constNum=0; int num1=0; int num2=0; int minNum=0; public int lowestCommonAncestor (TreeNode root, int p, int q) { if (null == root || p==q) return 0; num1=p; num2=q; process(root); return minNum; }

void process(TreeNode root){ dfs(root); //根节点都没有找到直接返回 if(constNum<2) return; if(constNum==2) minNum=root.val; constNum=0; process(root.left); if(constNum==1) return; if(constNum==2) minNum=root.val;

    //因为本题保证二叉树中每个节点的val值均不相同，所以如果遍历完左子树之后constNum，就没有必要再去遍历右子树
    if(constNum==0){
       process(root.right);
    }
}

void dfs(TreeNode root) {
    if(constNum<2){
        if (null == root) return;
        if (root.val==num1 || root.val==num2) constNum++;
        dfs(root.left);
        dfs(root.right);
    }
}

}