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

1、题目描述

 2、题目分析

求【二叉搜素树】的公共祖先，首先先了解基础概念，二叉搜索树的特性的特有特性。

          二叉搜索树的特性，二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

2-1、根据数值进行判定

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while(true){
           //p,q 节点比 目标祖先值 都大，那么可以到当前节点的右子节点寻找
           if(ancestor.val < p.val && ancestor.val < q.val){
               ancestor = ancestor.right;
           }else if(ancestor.val > p.val && ancestor.val > q.val){
                ancestor = ancestor.left;
           }else
                break;
           
        }
        return ancestor;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n是给定的二叉搜索树中的节点个数。分析思路与方法一相同。

• 空间复杂度：O(1)。

2-2、代码进行递进

逻辑思路根上面完全一致，代码可以进行精简优化。

• 如果根节点和 p,q 的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说比如上面的 p , q 在 root 的同一侧验证，可以通过 ( p.val - root.val ) * ( q.val - root.val ) > 0  的方法进行校验。
• 如果相乘的结果是负数，说明 p 和 q 位于根节点的两侧，如果等于 0，说明至少有一个就是根节点。
• 上面的代码优化如下：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //满足条件则说明，p和q在同一侧
        while((p.val-root.val)*(q.val-root.val) > 0){
           //p,q 节点比 目标祖先值 都大，那么可以到当前节点的右子节点寻找
           root = (root.val > p.val)?root.left:root.right;
           
        }
        //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n是给定的二叉搜索树中的节点个数。分析思路与方法一相同。

• 空间复杂度：O(1)。