【二叉树】求层序二叉树LCA

如上图所示,由正整数1, 2, 3, …组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从10到根结点的路径是(10, 5, 2, 1),从4到根结点的路径是(4, 2, 1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1)。对于两个结点x和y,假设他们到根结点的路径分别是(x1, x2, … ,1)和(y1, y2, … ,1)(这里显然有x = x1,y = y1),那么必然存在两个正整数i和j,使得从xi 和 yj开始,有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,… 现在的问题就是,给定x和y,要求xi(也就是yj)。输入输入只有一行,包括两个正整数x和y,这两个正整数都不大于1000。输出输出只有一个正整数xi。样例输入

10 4

样例输出

2

 

分析:

分析
属于LCA中最简单的层序问题,节点间有明朗的关系可以用于运算。一个节点的父亲可以通过编号除以2向下取整得到,于是乎可以通过递归对层数比较深的节点进行向上求LCA,当发现两个节点的结果相同时,即可认定为找到了共同的LCA。
#include <iostream>
using namespace std;
int LCA(int x, int y){return x == y ? x : (x > y ? LCA(x / 2, y) : LCA(x, y / 2));}
int main()
{
  int x, y;
  cin >> x >> y;
  cout << LCA(x, y) << endl;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × 5 =