首页 > 试题广场 >

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

[编程题]二叉搜索树的最近公共祖先
  • 热度指数:78039 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:


示例1

输入

{7,1,12,0,4,11,14,#,#,3,5},1,12

输出

7

说明

节点1 和 节点12的最近公共祖先是7   
示例2

输入

{7,1,12,0,4,11,14,#,#,3,5},12,11

输出

12

说明

因为一个节点也可以是它自己的祖先.所以输出12   

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {

        // 随便给2个数,利用二叉搜索树的性质:
        
        // 如果两个值都小于根节点,说明祖先在左子树一侧
        if(p<root.val && q<root.val)
            return lowestCommonAncestor(root.left,p,q);
        // 如果两个值都大于根节点,说明祖先在右子树一侧
        if(p>root.val && q>root.val)
            return lowestCommonAncestor(root.right,p,q);
        // 剩最后一种情况:如果根节点的值恰好在两个给定值之间,这个根节点就是最近的公共祖先
        return root.val;
    }
}

发表于 2022-01-05 21:39:02 回复(8)
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // p q在当前根的左右侧,直接返回根, 因为无论p 和 q 处于什么位置,它的祖先必然是当前的根
        if((p <= root.val && q >= root.val) || (p >= root.val && q <= root.val))
            return  root.val;
        
        // 两个数在根的左侧  左递归
        if(p < root.val) return  lowestCommonAncestor (root.left, p, q);
        // 否则右递归
        return  lowestCommonAncestor (root.right, p, q);
        
    }
}

发表于 2022-11-07 14:03:39 回复(0)
public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root.val<p&&root.val<q){
            return lowestCommonAncestor(root.right,p,q);
        }
        if (root.val>p&&root.val>q){
            return lowestCommonAncestor(root.left,p,q);
        }
        return root.val;
    }

发表于 2021-11-16 21:44:45 回复(0)
1.如果当前节点值比p和q都小,证明q与p在当前节点右子树中,应该在右子树中找
2.如果当前节点值比p和q都大,证明q与p在当前节点左子树中,应该在左子树中找
3.如果当前节点值介于p和q之间,证明找到了

ps:在二叉树中找最近公众祖先的方法也可以用在这里,不过没有利用二叉搜索树特有的性质
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        TreeNode *resNode = root;
        while(1){
            if(resNode->val < p && resNode->val < q){
                resNode = resNode->right;
            } else if(resNode->val > p && resNode->val > q){
                resNode = resNode->left;
            } else{
                break;
            }
        }
        return resNode->val;
        
        //没有考虑二叉搜索树的性质
//         if(root == nullptr) return -1;
//         if(root->val == p || root->val == q){
//             return root->val;
//         }
//         int left = lowestCommonAncestor(root->left, p, q);
//         int right = lowestCommonAncestor(root->right, p, q);
//         if(left != -1 && right != -1) return root->val;
//         if(left != -1) return left;
//         if(right != -1) return right;
//         return -1;        
    }
};








发表于 2021-11-11 10:32:28 回复(1)
void findpath(struct TreeNode *t,int path[],int *k,int x){
    if(t==NULL)return;
    int count=0;
    while(t->val!=x){
        path[count++]=t->val;//加入路径
        if(x<t->val){//小的在左子树
            t=t->left;
        }else{//大的在右子树
            t=t->right;
        }
    }
    path[count++]=t->val;
    *k=count;
}
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    int path1[10000],path2[10000],k1=0,k2=0,ans;
    findpath(root, path1, &k1, p);//找到根到p的路径
    findpath(root, path2, &k2, q);//找到根到q的路径
    for(int i=0,j=0;i<k1&&j<k2;i++,j++){
        //最后一个相同的节点就是最近公共祖先
        if(path1[i]==path2[j]){
            ans=path1[i];
        }else{
            break;
        }
    }
    return ans;
}

发表于 2022-11-03 17:41:06 回复(0)
int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(p<root->val && q<root->val)    return lowestCommonAncestor(root->left,p,q);
        if(p>root->val && q>root->val)    return lowestCommonAncestor(root->right,p,q);
        return root->val;
    }


发表于 2022-08-03 16:03:12 回复(0)
function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
    if (root === null) return null;
    let min = Math.min(p,q);
    let max = Math.max(p,q);
    if (root.val === min || root.val === max) return root.val // 有一个是根节点
    if (min < root.val && max > root.val) return root.val    // 一左一右
    if (root.val > min && root.val > max) { // 都在左树
        return lowestCommonAncestor(root.left, p,q);
    }
    if (root.val <min && root.val <max ) {  // 都在右树
        return lowestCommonAncestor(root.right, p,q);
    }
}
发表于 2021-12-07 09:49:24 回复(0)
class Solution:
    def lowestCommonAncestor(self , root , p , q ):
        # write code here
        if not root:
            return None
        if root.val <p and root.val<q:
            return self.lowestCommonAncestor(root.right,p,q)
        if root.val>p and root.val>q:
            return self.lowestCommonAncestor(root.left,p,q)
        return root.val

发表于 2021-11-17 10:23:07 回复(1)
我发现了一个 bug
int x = pList.get(i);
int y = qList.get(i);   // 不能直接 pList.get(i) == qList.get(i) 比较。必须得声明一个变量比。。。。
if (x == y) {
    res = x;
} else {
    break;  
}

发表于 2023-08-06 16:40:45 回复(1)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // 时间复杂度O(N),空间复杂度O(N)
        if (p < root->val && q < root->val) return lowestCommonAncestor(root->left, p, q);
        else if (p > root->val && q > root->val) return lowestCommonAncestor(root->right, p, q);
        else return root->val;
    }
};

发表于 2022-10-10 17:46:54 回复(0)
/*
    本题思路:
    1.如果两个结点p、q在树的两边,那么公共结点就是根结点
    2.如果两个结点都在左子树,那么递归以左子树为根节点即可;如果两个结点都在右子树,那么递归以右子树为根节点即可;
    */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        //在树的两边
        if((p<=root.val&&q>=root.val)||(q<=root.val&&p>=root.val)){
            return root.val;
        }
        //都在左子树
        if(p<root.val&&q<root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else{   //都在右子树
            return lowestCommonAncestor(root.right,p,q);
        }
    }

发表于 2022-05-17 16:06:27 回复(0)
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        return fun(root, p, q)->val;
    }
    static TreeNode* fun(TreeNode* T, int p, int q) {
        if (p < T->val && q < T->val)
            return fun(T->left, p, q);
        else if (p > T->val && q > T->val)
            return fun(T->right, p, q);
        else return T;
    }
};

发表于 2022-03-15 21:28:37 回复(0)
可以递归,也可以直接用子节点向上追溯求交点
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null) {
                queue.offer(node.left);
                map.put(node.left.val, node);
            }
            if(node.right != null) {
                queue.offer(node.right);
                map.put(node.right.val, node);
            }
        }
        // 用p向上追溯,记录沿途节点的值
        HashSet<Integer> path = new HashSet<>();
        int cur = p;
        path.add(cur);
        while(map.get(cur).val != cur){     // 还未到根节点
            cur = map.get(cur).val;
            path.add(cur);
        }
        cur = q;
        while(!path.contains(cur)) cur = map.get(cur).val;
        return cur;
    }
}

发表于 2021-11-20 21:52:18 回复(0)
不看解题是想不出来,本来脑海里构思了一万行,有点怀疑就没去敲,看了解题思路,原来。。。
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    if(p<root->val && q<root->val) 
        return lowestCommonAncestor(root->left, p, q);
    else if(p>root->val && q>root->val) 
        return lowestCommonAncestor(root->right, p, q);
    else 
        return root->val;
}

编辑于 2024-03-16 22:59:04 回复(0)
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        while((root.val > p and root.val > q)or(root.val < p and root.val < q)):
            if (root.val > p and root.val > q):
                root = root.left
            else:
                root = root.right
        return root.val

发表于 2023-07-26 15:25:27 回复(0)
超简单思路:
    // 算法思路
    /**
     * 将元素按升序进行排序 获取升序数组
     * 根据二叉搜索树 + 最近公共祖先的特性,最近公共祖先一定在[node(p), node(q)]之间。故此通过P,q获取升序子区间
     * 最后遍历升序子区间[node(p), node(q)] 获取node节点树, 根据dfs算法 判断当前节点能否同时找到 p q 如果能 说明是最近公共祖先
    */
export function lowestCommonAncestor(root: TreeNode, p: number, q: number): number {
    // write code here
    // 算法思路
    /**
     * 将元素按升序进行排序 获取升序数组
     * 根据二叉搜索树 + 最近公共祖先的特性,最近公共祖先一定在[node(p), node(q)]之间。故此通过P,q获取升序子区间
     * 最后遍历升序子区间[node(p), node(q)] 获取node节点树, 根据dfs算法 判断当前节点能否同时找到 p q 如果能 说明是最近公共祖先
    */
    let array:Array<TreeNode> = []
    inorder(root, array)
    array = getSubArray(array, p, q)

    for(let node of array) {
        if (dfs(node, p) && dfs(node, q)) return node.val
    }
    return root.val
}

// 将元素按升序进行排序
const inorder = (root: TreeNode, array:Array<TreeNode>) => {
    if(root === null) return
    inorder(root.left, array)
    array.push(root)
    inorder(root.right, array)
}
// 锁定查找最近公共祖先的元素区间
const getSubArray = (array:Array<TreeNode>, p: number, q: number) => {
    let left = 0
    let right = array.length - 1
    for(let i = 0 ; i < array.length; i++) {
        if (array[i].val === p) left = i
        if (array[i].val === q) right = i
    }

    return array.splice(left, right)
}
// 通过dfs判断在节点数能否找到目标值
const dfs = (root: TreeNode, target:number) => {
    if(root === null) {
        return false
    } 
    if(root.val === target) {
        return true
    }
    return dfs(root.left, target) || dfs(root.right, target)
}


发表于 2023-06-30 00:44:27 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        auto s = min(p, q);
        auto l = max(p, q);

        if (root->val < s) {
            return lowestCommonAncestor(root->right, p, q);
        }

        if (root->val > l) {
            return lowestCommonAncestor(root->left, p, q);
        }

        return root->val;
    }
};

发表于 2023-04-11 00:07:20 回复(0)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(root->val<p&&root->val<q)
            return lowestCommonAncestor(root->right, p, q);
        if(root->val>p&&root->val>q)
            return lowestCommonAncestor(root->left, p, q);
        return root->val;
    }
};

发表于 2023-03-31 16:45:24 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        int min  = Math.min(p, q);
        int max = Math.max(p, q);

        //当root.val大于min,同时大于max,则公共祖先节点在左子树
        if (root.val > min && root.val > max)
            return lowestCommonAncestor(root.left, p, q);

        //当root.val大于min,同时大于max,则公共祖先节点在右子树
        if (root.val < min && root.val < max)
            return lowestCommonAncestor(root.right, p, q);

        /**
            只剩下两种情况:
            1.当root.val等于min或者max,则为root.val
            if (root.val == min || root.val == max)
                return root.val;
            2.当root.val小于左边大于右边,则为root.val
            if (root.val > min && root.val < max)
                return root.val;
         */
        return root.val;
    }
}

发表于 2022-09-19 15:10:23 回复(0)
func lowestCommonAncestor( root *TreeNode ,  p int ,  q int ) int {
    // write code here
    tmp:=root
    for{
        if p< tmp.Val && q<tmp.Val{
            tmp=tmp.Left
        }else if p>tmp.Val && q >tmp.Val{
            tmp=tmp.Right
        }else{
            return tmp.Val
        }
    }
}

发表于 2022-04-05 01:46:00 回复(1)