【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先-跟着帅地玩副业，开拓第二曲线PlayOffer

岱永久会员 2025年1月8日下午4:43

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

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;
            }else if(root.val > p.val && root.val > q.val)// p,q 都在 root 的左子树中
            {
                root = root.left;
            }else break;
        }
        return root;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月24日下午5:13

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root != NULL){
            if(p->val > root->val && q->val > root->val){
                root = root->right;
            }
            else if(p->val < root->val && q->val < root->val){
                root = root->left;
            }
            else{
                return root;
            }
        }
        return NULL;
    }
};

利用二叉搜索树的特性求解，在同侧则向其方向搜索，在两侧直接返回结果

0 赞同 0 条回复

陆狗陆狗普通 2024年12月7日下午2:08

解题思路
– 二叉搜索树任意节点（包括根节点）左边金额<节点金额<右边金额
– 2个节点的分布可能都在根节点左侧（递归），或者右侧（递归），或者双侧（根节点就是CommonAncestor）
【题解1】

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        if (p.val == q.val) {
            return p;
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

0 赞同 0 条回复

晓宇普通 2024年12月3日下午8:30

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root->val > p->val && root->val > q->val) root = root->left;
            else if(root->val < p->val && root->val < q->val) root = root->right;
            else return root;
        }
        return nullptr;
    }
    // 利用二叉搜索树的数值关系锁定节点位置
    // 时间复杂度：o(n);空间复杂度:o(1)
};

0 赞同 0 条回复

Aatorx 永久会员 2024年12月3日下午3:36

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root != nullptr) {
            if(root->val < p->val && root->val < q->val){
                root = root->right;
            }
            else if(root->val > p->val && root->val > q->val){
                root = root->left;
            }
            else {
                return root;
            }
        }
        return nullptr;
    }
};

时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

Jerry 普通 2024年12月2日下午11:09

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root->val > p->val && root->val > q->val){
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(root->val < p->val && root->val < q->val){
            return lowestCommonAncestor(root->right, p, q);
        }
        else{
            return root;
        }
        return NULL;
    }
};

一开始没想出来，看了答案写的
刚开始想：分别记录从root到p、q的path路径，然后遍历路径直到p或q

0 赞同 0 条回复

lQl 永久会员 2024年12月2日下午8:38

递归
时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月2日下午7:15

思路：使用搜索树性质

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null){
            return null;
        }

        if(root.val >= p.val && root.val <= q.val){
            return root;
        }

        if(root.val == p.val || root.val == q.val){
            return root;
        }        

        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }

        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }

        return root;
    }


}

0 赞同 0 条回复

黑键〰普通 2024年12月2日下午3:43

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root == null) return root
    let res = new TreeNode(0)
    const findp = (root) => {
        if(p.val > root.val && q.val > root.val) {
            findp(root.right)
        } else if (p.val < root.val && q.val < root.val) {
            findp(root.left)
        } else {
            res = root
        }
        return res
    }
    return findp(root)
};

思路：二叉搜索树的特性，比较根节点的值和p q的值

0 赞同 0 条回复

遇事不决睡大觉普通 2024年12月1日下午5:11

/**
* 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) {
int min = Math.min(p.val, q.val);
int max = Math.max(p.val, q.val);
TreeNode lca = root;
while (root != null) {
if (root.val >= min && root.val <= max) {
lca = root;
break;
} else if (root.val > max) {
root = root.left;
} else if (root.val < min) {
root = root.right;
}
}
return lca;
}
}//二份查找

0 赞同 0 条回复

Xiang. 永久会员 2024年12月1日下午3:35

思路：区别于普通二叉树的最近公共祖先，二叉搜索树无需自底向下进行回溯，而是利用搜索树的性质，直接从根节点处向下寻找，当找到第一个root的值满足不恒大于p、q或不恒大于p、q的即为最近公共祖先
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return root;
        if(root.val>p.val&&root.val>q.val){
            TreeNode left=lowestCommonAncestor(root.left,p,q);
            if (left!=null) return left;
        }
        if(root.val<p.val&&root.val<q.val){
            TreeNode right=lowestCommonAncestor(root.right,p,q);
            if (right!=null) return right;
        }
        return root;
    }
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

jaron 普通 2024年12月1日下午2:12

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val < Math.min(p.val, q.val)) {
                // 比两个子节点都小，往右移动
                root = root.right;
            } else if (root.val > Math.max(p.val, q.val)) {
                // 比两个子节点都大，往左移动
                root = root.left;
            } else {
                // 如果先遇到了p，说明p是答案
                // 如果先遇到了q，说明q是答案
                // 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案
                return root;
            }
        }
        return root;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年12月1日下午1:55

//时间复杂度O(N)空间复杂度和树高度相关
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root null) return null;

    if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); 
    if(p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);

    return root;
}

}

0 赞同 0 条回复

Renasc 普通 2024年12月1日上午10:08

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            // 如果root值都大于p和q，说明公共祖先在左子树
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {  // 如果root值都小于p和q，说明公共祖先在右子树
                root = root.right;
            } else {   // 如果一大一小，说明root就是最近公共祖先
                return root;
            }
        }

        return null;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年11月30日下午11:04

若p和q一个比当前节点大一个小，则最近祖先就是当前节点，若都小，就在当前节点左边，若都大，就在当前节点右边

/**
 * 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(p.val<root.val&&q.val<root.val){
                root=root.left;
            }else if(p.val>root.val&&q.val>root.val){
                root=root.right;
            }else {
                break;
            }
        }
        return root;
    }

}

on on

0 赞同 0 条回复

迢迢星野普通 2024年11月30日下午9:22

class Solution {
    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 
     * 题意解读：求两个指定二叉树根节点的最近公共祖先
     * p 和 q 在 node 节点的两侧，说明 node 是所求的最近公共祖先
     * p 在 q 的子树中，说明 q 就是所求的最近公共祖先
     * q 在 p 的子树中，说明 p 就是所求的最近公共祖先
     * 
     * 在二叉搜索树中，
     * 如果 p 和 q 的值都小于 node 的值，说明 p 和 q 在 node 的左子树中.
     * 如果 p 和 q 的值都大于 node 的值，说明 p 和 q 在 node 的右子树中.
     * 如果 p 和 q 的值在 node 的两侧，说明 node 就是 p、q 的最近公共祖先。
     * 
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 保证 p 节点的值是 <= q 的节点
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        return find(root, p, q);
    }

    private TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (p.val <= root.val && q.val >= root.val) {
            // p、q 在 root 的两侧，说明 root 就是 p、q 的最近公共祖先
            return root;
        }

        if (q.val < root.val) {
            // 说明 p、q 在 root 的左子树中
            return find(root.left, p, q);
        } else {
            // 说明 p、q 在 root 的右子树中
            return find(root.right, p, q);
        }
    }
}

思路：参考注释
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午9:07

/**
解题思路：递归
根据二叉搜索树性质. left < root < right
如果root>p && root>q,说明最近公共祖先在左子树,递归搜索
如果root=p && root<=q,说明最近公共祖先是root or q or q,返回即可

时间复杂度 O(N)
空间复杂度，最坏情况二叉搜索树为单链表形式，最大递归深度为O(N)
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

0 赞同 0 条回复

苯庸普通 2024年11月30日下午8:09

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root null){
return root;
}
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}
if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

共以下 18 个回答

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

# 回答此问题取消回复

【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

共以下 18 个回答

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

# 回答此问题 取消回复

# 回答此问题取消回复