ACM-二叉树

问题描述

      满二叉树

        如上图所示，由正整数 1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号是 1 的结点）都有一条唯一的路径，比如从 10 到根结点的路径是(10, 5, 2, 1)，从 4 到根结点的路径是(4, 2, 1)，从根结点 1 到根结点的路径上只包含一个结点 1，因此路径就是(1)。对于两个结点 x 和 y，假设他们到根结点的路径分别是(x₁, x₂, ... ,1)和(y₁,y₂, ... ,1)（这里显然有 x = x₁， y = y₁），那么必然存在两个正整数 i 和 j，使得从 x_i 和 y_j开始，有 x_i = y_j ， x_i + 1 = y_j + 1， x_i + 2 = y_j + 2， ... 现在的问题就是，给定 x 和 y，要求 x_i（也就是 y_j）。

输入数据

        输入只有一行，包括两个正整数 x 和 y，这两个正整数都不大于 1000。

输出要求

        输出只有一个正整数 x_i。

输入样例

10 4

输出样例

2

解题思路

        这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对 2 做整数除法，就走到它的上层结点。         我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，直到它们相遇。设 common(x, y)表示整数 x 和 y的最近公共子节点，那么，根据比较 x 和 y 的值，我们得到三种情况：

1) x 与 y 相等，则 common(x, y)等于 x 并且等于 y； 2） x 大于 y，则 common(x, y)等于 common(x/2, y)； 3） x 大于 y，则 common(x, y)等于 common(x y/2)；

参考程序

#include <iostream> using namespace std; int common(int x,int y){ if(x == y){ return x; }else if(x > y){ return common(x/2,y); }else{ return common(x,y/2); } } int main() { int x,y; cin >> x >> y; cout << common(x,y) <<endl; return 0; }