二叉树

先统一了两个数所在的层数，再根据int(n/2)寻找上一个节点的值进行比较

#include<cmath>
using namespace std;

int main(){
    int a, b;
    while(cin >> a >> b){
        int a_layer, b_layer;
        a_layer = (int)(log(a) / log(2)) + 1;
        b_layer = (int)(log(b) / log(2)) + 1;
        //cout << a_layer << ' ' << b_layer << endl;
        while(a_layer > b_layer){
            a = (int)(a / 2);
            a_layer--;
            //cout << a << endl;
        }
        while(b_layer > a_layer){
            b = (int)(b / 2);
            b_layer--;
        }
        while(a != b){
            a = (int)(a / 2);
            b = (int)(b / 2);
            //cout << a << ' ' << b << endl;
        }
        cout << a << endl;
    }
    return 0;
}

try:
    while True:
        a,b = list(map(int,input().split()))
        while a != b:
            if a < b:
                b //= 2
            else:
                a //= 2
        print(a)
except Exception:
    pass

import java.util.*;
 
public class Main {
    public static double getLevel(int a)  {
        return Math.log(a)/Math.log(2);
    }
    
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            int x = reader.nextInt();
            int y = reader.nextInt();
            int levelx = (int)getLevel(x);
            int levely = (int)getLevel(y);
            while (levelx != levely) {
                if (levelx > levely) {
                    x /= 2;
                    levelx = (int)getLevel(x);
                } else {
                    y /= 2;
                    levely = (int)getLevel(y);
                }
            }
            while (x != y && x > 1 && y > 1) {
                x = x / 2;
                y = y / 2;
            }
            System.out.println(x);
        }
    }
}

#include<stdio.h>
int main()
{
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        while(x!=y)//一直循环到相等为止
        {
            if(x>y)//大的数要找上一个节点
                x/=2;
            else
                y/=2;
        }
        printf("%d\n",x);
    }
}

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int x,y;
    while(cin>>x>>y){
        int ma=x>y? x:y;    int mi=x<y? x:y;
        while(ma>mi)
            ma/=2;
        if(ma==mi)    cout<<mi<<endl;
        else{    //    统一层数再同时往下找
            if(floor(log(ma)/log(2))!=floor(log(mi)/log(2)))
                mi/=2;
            while(ma!=mi){
                mi/=2;    ma/=2;
            }
            cout<<ma<<endl;
        }
    }
    return 0;
}

#include<stdio.h>
int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF){
        while(a-b)
            if(a>b) a/=2;
            else b/=2;
        printf("%d\n",a);
    }
}

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int m,n;
	while (cin >> m >> n)
	{
		while (m != n)
		{
			if (m > n) m >>= 1;
			else n >>= 1;
		}

		cout << m << endl;
	}

	return 0;
}

#include<iostream>
using namespace std;
int PubParent(int x,int y){
	if(x == y)
		return x;
	else if(x == (y+1) && y == (x+1))
		return x/2;
	else{
		if(y>x)
			return PubParent(x,y/2);
		else
			return PubParent(x/2,y);
	}
}

int main(){
	int x,y;
	while(scanf("%d %d",&x,&y)!=EOF)
		cout<<PubParent(x,y)<<endl;
	return 0;
}

解法一

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

public class Main {

	public static void main(String[] args) {
		/****************************解法一******************************/
		Scanner scanner = new Scanner(new BufferedInputStream(System.in));
		while (scanner.hasNext()) {
			int node1=scanner.nextInt();
			int node2=scanner.nextInt();
			ArrayList<Integer> list1=new ArrayList<>();
			GetParentNodeList(node1, list1);
			ArrayList<Integer> list2=new ArrayList<>();
			GetParentNodeList(node2, list2);
			int last=0;
			if (list1.size()>list2.size()) {
				for (int i = 0; i<list2.size(); i++) {
					if (list1.contains(list2.get(i))) {
						last=list2.get(i);
						break;
					}
				}
			}else {
				for (int i = 0; i<list1.size(); i++) {
					if (list2.contains(list1.get(i))) {
						last=list1.get(i);
						break;
					}
				}
			}
			System.out.println(last);
		}
		scanner.close();
	}
	
	private static List<Integer> GetParentNodeList(int node,List<Integer> list) {
		if (node==1) {
			list.add(1);
			return list;
		}else {
			list.add(node);
			list=GetParentNodeList(node/2, list);
		}
		return list;
	}
}

解法二

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		/****************************解法二******************************/
		Scanner scanner = new Scanner(new BufferedInputStream(System.in));
		while (scanner.hasNext()) {
			int node1=scanner.nextInt();
			int node2=scanner.nextInt();
			while(node1!=node2){
				if (node1>node2) {
					node1/=2;
				}else {
					node2/=2;
				}
			}
			System.out.println(node1);
		}
		scanner.close();
	}
}

#include<stdio.h>
 
int main()
{
    int x,y;
    while(scanf("%d%d",&x,&y) != EOF){
        while(x != y){
            if(x<y){
                y = y/2;
            }else{
                x = x/2;
            }
        }
        printf("%d\n",x);
    }
    return 0;   
}  

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int x, y;
    while (cin >> x >> y) {
        stack<int>s1, s2;   //用堆栈存储x和y结点到根结点的路径
        while (x) {
            s1.push(x); //路径结点入栈
            x /= 2;     //追溯父节点
        }
        while (y) {
            s2.push(y); //路径结点入栈
            y /= 2;     //追溯父节点
        }
        int father = 1; //公共父节点
        //逆向遍历路径，找第一个非公共父节点，其前面一个结点即为首个公共父节点
        while (!s1.empty() && !s2.empty() && s1.top() == s2.top()) {
            father = s1.top();  //访问栈顶元素
            s1.pop();           //出栈
            s2.pop();           //出栈
        }
        cout << father << endl;
    }
    return 0;
}

#include <cstdio>

int main()
{
    int x, y;
    while (scanf("%d %d", &x, &y) != EOF)
    {
        while (true)
        {
            if (x == y)
                break;
            else if (x > y)
                x /= 2;
            else 
                y /= 2;
        } 
        printf("%d\n", x);
    }
    return 0;
}