问题描述
在一个神奇的二叉树中,结构非常独特:
每层的节点值赋值方向是交替的,第一层从左到右,第二层从右到左,以此类推,且该二叉树有无穷多层。
小R对这个二叉树充满了好奇,她想知道,在二叉树中两个节点之间x, y
的路径长度是多少。
graph TD1((1));2((2));3((3));4((4));5((5));6((6));7((7));8((8));9((9));10((10));11((11));1---3;1---2;3---4;3---5;2---6;2---7;6---11;6---10;7---9;7---8;
测试样例
示例 1:
输入:
x = 11, y = 4
输出:5
示例 1:
输入:
x = 2, y = 5
输出:3
示例 1:
输入:
x = 7, y = 7
输出:0
题解:
因为每层的个数都是上一层乘二,同时是个,n为层数。所以就是x,y所在的层数。接着通过层高的奇偶性判断排列的顺序,再与x,y相减便可得到所在的位置。最后一层一层向上找相同的根即可得到路程。
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;int countplace(int dx,int x){int i,cnt=0;if(dx%2==1){return pow(2,dx)-(x-pow(2,dx));}else{return x-pow(2,dx)+1;}
}int solution(int x, int y) {// write code hereif(x<y){int tt=x;x=y;y=tt;}int i,j,k,t=max(x,y),maxi=0;int dx=0,dy=0,px=0,py=0,lx=0,ly=0;dx=log2(x);dy=log2(y);cout << dx << " " << dy << "\n";px=countplace(dx,x);py=countplace(dy,y);/*if(dx==dy){return abs(px-py);}*/while(dx!=dy){if(px%2!=0){px++;}px/=2;dx-=1;lx++;}while(px!=py){if(px%2!=0){px++;}if(py%2!=0){py++;}px/=2;dx-=1;lx++;py/=2;dy-=1;ly++;}//cout << lx+ly << "\n";return lx+ly;
}int main() {std::cout << (solution(11, 4) == 5) << std::endl;std::cout << (solution(2, 5) == 3) << std::endl;std::cout << (solution(7, 7) == 0) << std::endl;std::cout << (solution(383786261, 653995378)==57) << std::endl;std::cout << (solution(997295150, 889335947)==56) << std::endl;return 0;
}