题解 | #二叉搜索树的最近公共祖先#
递归根据条件进行判断，如果p和q分别大于或小于遍历到的当前节点的值，那么肯定当前节点是祖先，如果p和q都大于当前节点值，那么就找当前节点的右子树，否则找左子树。直到找到p和q分别大于或小于遍历到的当前节点的值。
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param p int整型
* @param q int整型
* @return int整型
*/
function lowestCommonAncestor( root , p , q ) {
// write code here
return dfs(root)
function dfs(node){
if(!node) return -1
//p和q分别大于或小于遍历到的当前节点的值
if((p>=node.val&&q<=node.val)||(p<=node.val&&q>=node.val)){
return node.val
}
//p和q都大于当前节点值，那么就找当前节点的右子树
if(p > node.val && q > node.val){
return dfs(node.right)
}
if(p<node.val&&q<node.val){
return dfs(node.left)
}
}
}
module.exports = {
lowestCommonAncestor : lowestCommonAncestor
};
查看14道真题和解析
投递美团等公司10个岗位
