目录

• • 题目
  • 算法思路
  • 方法一-迭代
  • 方法二-递归
  • 参考

题目

算法思路

所谓的 【最近公共祖先】，也就是说 r o o t root root 是节点 p p p 和 q q q 的公共祖先，且 r o o t . l e f t root.left root.left 、 r o o t . r i g h t root.right root.right 都不是节点 p p p 和 q q q 的公共祖先，可能的位置关系为：

1. p p p 和 q q q 分别位于 r o o t root root 的左右子树中；
2. p = r o o t p=root p=root，且 q q q 位于 r o o t root root 的子树中；
3. q = r o o t q=root q=root，且 p p p 位于 r o o t root root 的子树中。

因为是二叉搜索树，所以我们可以 利用节点的值的大小关系来判断位置关系 。

方法一-迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            if(root.val < p.val && root.val < q.val){//若p,q均在root右子树
                root = root.right;//遍历至root的右子节点
            }else if(root.val > p.val && root.val > q.val){//若p,q均在root左子树
                root = root.left;//遍历至root的左子节点
            }else break;//否则跳出循环,当前的root就是最近公共祖先
        }
        return root;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)，n 为二叉树节点总数，实际上时间开销为二叉树的层数，最小为 l o g n logn logn（满二叉树），最大为 n （退化为链表）。
• 空间复杂度： O ( 1 ) O(1) O(1)

代码优化：
先确定节点 p p p 和 q q q 的大小关系，可以减少判断条件

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //确保p的值小于等于q的值
        if(p.val > q.val){
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }
        while(root != null){
            if(root.val < p.val){//若p,q均在root右子树
                root = root.right;//遍历至root的右子节点
            }else if(root.val > q.val){//若p,q均在root左子树
                root = root.left;//遍历至root的左子节点
            }else break;//否则跳出循环,当前的root就是最近公共祖先
        }
        return root;
    }
}

方法二-递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val){//若p,q均在root右子树
            return lowestCommonAncestor(root.right, p, q);//递归至root的右子树
        }else if(root.val > p.val && root.val > q.val){//若p,q均在root左子树
            return lowestCommonAncestor(root.left, p, q);//递归至root的左子树
        }
        return root;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)，n 为二叉树节点总数，实际上时间开销为二叉树的层数，最小为 l o g n logn logn（满二叉树），最大为 n （退化为链表）。
• 空间复杂度： O ( n ) O(n) O(n)，树退化为链表时，递归深度达到 n

参考

参考