我要招人

去企业版

首页 > 试题广场 >

最近公共祖先

[编程题]最近公共祖先

热度指数：13091 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例：

2，3

返回：1

算法知识视频讲解

推荐

九城城主

//思路：满二叉树的子节点与父节点之间的关系为root = child / 2

//利用这个关系，如果a ！= b，就让其中的较大数除以2，如此循环知道a == b，

//即是原来两个数的最近公共祖先

//代码如下：

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        while(a != b)
            {
            if(a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};

编辑于 2015-08-17 19:01:23 回复(34)

Java

抓住努力的尾巴

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        while(a != b) {
            if(a > b) {
                a /= 2;
            }
            if(a < b) {
                b /= 2;
            }
        }
        return a;
    }
}

发表于 2022-04-06 16:51:18 回复(0)

Java

来学习的小张

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        while( a != b){
            if( a > b){
                 a /= 2;
            }else if(a < b){
                 b /= 2;
            }
        }
        return a;
    }
}

发表于 2022-04-02 19:02:02 回复(0)

Java

Raymond🌽

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        List<Integer> list = new ArrayList<>();
        while(a != 0){
            list.add(a);
            a/=2;
        }
        while(b != 0){
            if(list.contains(b))
                return b;
            b/=2;
        }
        return 1;
    }
}

没有使用递归，用 list + 两次循环。简单处理

发表于 2022-01-04 09:52:31 回复(0)

Java

offer不好吃

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {

        return a == b ? a :(a > b ? getLCA(a>>1,b) : getLCA(a,b>>1));
    }
}

发表于 2021-06-04 17:24:34 回复(1)

Java

codewind

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        /*
                   1
                 2    3
                4  5  6  7
        
        */
        Op op = new Op();
        op.getParent(a,b);
        return op.parent;
        
        
        
    }
    
    static class Op{
        int parent = -1;
        void getParent(int nodea,int nodeb) {
            while(nodea!=nodeb) {
                if(nodea> nodeb) {
                    nodea>>=1;
                }else{
                    nodeb>>=1;
                }
            }
            parent = nodea;
        }
    }
    
    
}

发表于 2020-10-29 14:00:55 回复(0)

Java

4.435km/s

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LCA {
    public static int getLCA(int a, int b) {
        // write code here
        List<Integer> lista = new ArrayList<>();
        List<Integer> listb = new ArrayList<>();
        lista.add(a);
        listb.add(b);
        judge(a,lista );
        judge(b,listb );
        for(int a1:lista){
            for (int b1:listb){
                if(a1==b1){
                    return a1;
                }
            }
        }
        return 0;
    }
    public static void judge(int num,List<Integer> list){
        while(num>1){
            if(num%2==0) {
                num = num / 2;
                list.add(num);
            }else {
                num = (num-1)/2;
                list.add(num);
            }
        }
    }
}

发表于 2020-03-11 14:03:32 回复(0)

Java

笑话12347

//思路：节点n的左子节点是2n，右子节点是2n+1的特性。先让a和b处于同一层，然后向上找父节点  
//
public int getLCA(int a, int b) {
		// write code here
		if (a == b)
			return a;
		if (a > b) {
			int temp = a;
			a = b;
			b = temp;
		}
		// 保证a<b
		int aLayer = (int) (Math.log(a) / Math.log(2));
		int bLayer = (int) (Math.log(b) / Math.log(2));
		// 使a,b在同一层
		while (bLayer > aLayer) {
			if (b % 2 == 1) {
				b = b - 1;
			}
			b = b / 2;
			bLayer--;
		}
		int aParent = a,bParent =b;
		while(aParent!=bParent){
			if(aParent%2==1)
				aParent --;
			if(bParent%2==1)
				bParent --;
			aParent /=2;
			bParent /=2;
		}
		return aParent;
	}

编辑于 2017-08-10 21:16:02 回复(0)

Java

村长，那人偷牛！

//方法一：开始看到这一题觉得递归搜索吧，这递归不好写啊，一看输入没有树，难道是找规律？画个图观察了一下，还真有规律。。QAQ，我是菜鸟我怕谁
public int getLCA(int a, int b) {
        if(a==b) return a;
        while(a!=b){
            a=a>b?a>>1:a;
            b=b>a?b>>1:b;
        }
        return a;
    }
//方法二：最近在学习递归，所以。。。。
 public int getLCA(int a, int b) {
        return a==b?b:a>b?getLCA(a>>1,b):getLCA(a,b>>1);
    }

编辑于 2017-05-13 17:11:00 回复(1)

Java

大闲人柴毛毛

思路

满二叉树的节点与父节点的关系为：节点值/2=父节点值。因此：当a!=b的时候就一直循环，将大的那个除以2，再比较是否相同，直到相同为止。

public int getLCA(int a, int b) {
    while ( a>=1 && b>=1 && a!=b ) {
        if ( a>b ) {
            a /= 2;
        }
        else {
            b /= 2;
        }
        if ( a==b ) {
            return a;
        }
    }
    return 0;
}

发表于 2017-03-31 11:30:59 回复(0)

Java

一神

写一个简单的版本：

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        int tmp;
        if (a > b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        
        while (a != b) {
            b = b / 2;
            if (b == a) {
                return b;
            } else if (b < a) {
                tmp = b;
                b = a;
                a = tmp;
            }
        }
        
        return 1;
    }
}

发表于 2017-02-15 10:50:04 回复(0)

Java