235. 二叉搜索树的最近公共祖先

时间：2021-04-06 20:34:33 收藏：0 阅读：12

技术分享图片

首先复习下二叉搜索树BST的概念，总结一下就是

1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树

参考了下大佬的解答，

如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。

时间O(logn)(这里有点近似于二分查找)，空间O(1)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
　　　　　//如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说 
        //他们肯定都位于根节点的同一侧，就继续往下找
        while((root.val-p.val)*(root.val-q.val)>0) {
            root = root.val>=p.val ? root.left:root.right;
        }
　　　　 //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return root;
    }

原文：https://www.cnblogs.com/jchen104/p/14622624.html