给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
分析:既然是二叉搜索树,那么一定要把这个条件用上,普通树我们只能从低向上去找公共祖先,但二叉搜索树我们可以自顶向下去考虑。若是节点的值比p大,比q小,那么他一定就是最近的公共祖先了!
参考代码:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(true){
if(root.val>p.val&&root.val>q.val){
root =root.left;
}
else if(root.val
}
else{
break;
}
}
return root;
}
