思路：
结论：root在p q中间, 则root一定是公共祖先！
利用二叉树左小右大的特点
使用前序遍历，只需要遍历部分子树而非遍历所有子树
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 利用左小右大的性质
// 只需遍历部分数
// 前序遍历
if(root==null){
return root;
}
// if 控制递归（BST常见模板），可无需终止条件
// 满足条件才去递归！而不是递归所有子树 ！
if(root.val>p.val && root.val>q.val){
TreeNode left=lowestCommonAncestor(root.left,p,q);
return left;
}
if(root.val<p.val && root.val<q.val){
TreeNode right=lowestCommonAncestor(root.right,p,q);
return right;
}
// root在p q中间,则root一定是公共祖先！
// 返回公共祖先！
return root;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89287.html
