当前位置:网站首页>Find the common ancestor of any two numbers in a binary tree
Find the common ancestor of any two numbers in a binary tree
2022-07-02 12:13:00 【weixin_ fifty million one hundred and seventy-nine thousand nin】
The code is as follows :
void Anales(int arr[],int p, int q)
{
int pos = -1;
int size = 0;
int as[1] = { 0 };
int indexP = 0;
int indexQ = 0;
while (arr[size] != as[1])
{
if (arr[size] == p)
{
indexP = size;
}
if (arr[size] == q)
{
indexQ = size;
}
size++;
}
if (indexP > indexQ)
{
int subInt = indexP - indexQ; // For example, the interval between indexes is exactly equal to the smaller index , So their male // The common ancestor index is 0
if (subInt == indexQ)
{
pos = 0;
}
else
{
int fatherP = indexP;
while (fatherP > indexQ)
{
if (fatherP % 2) // If the current index is even , Its upper level = ( Current index - 2)/2
{
fatherP = (fatherP - 2) / 2;
}
else // If the current index is odd , Its upper level = ( Current index - 1)/2
{
fatherP = (fatherP - 1) / 2;
}
}
if (fatherP == indexQ)
{
pos = fatherP;
}
else
{
// At the same time, look for superiors until they are equal
while (fatherP != indexQ)
{
if (fatherP % 2)
{
fatherP = (fatherP - 2) / 2;
}
else
{
fatherP = (fatherP - 1) / 2;
}
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
pos = indexQ;
}
}
}
else if (indexQ > indexP)
{
int subInt = indexQ - indexP;
if (subInt == indexP)
{
pos = 0;
}
else
{
while (indexQ > indexP)
{
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
if (indexP == indexQ)
{
pos = indexQ;
}
else
{
while (indexP != indexQ)
{
if (indexP % 2)
{
indexP = (indexP - 2) / 2;
}
else
{
indexP = (indexP - 1) / 2;
}
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
pos = indexQ;
}
}
}
else
{
pos = indexP;
}
std::cout << " Common ancestor :" << arr[pos] << "\t Indexes :" << pos << std::endl;
}
int main()
{
int arr[15] = { 3,5,1,6,2,0,8,0,0,7,4,0,0,0,0 };
Anales(arr,5,4);
}
边栏推荐
猜你喜欢
Fresh, 2022 advanced Android interview must know 100 questions (interview questions + answer analysis)
Small guide for rapid formation of manipulator (VII): description method of position and posture of manipulator
drools决策表的简单使用
深入理解P-R曲线、ROC与AUC
Mish shake the new successor of the deep learning relu activation function
Depth filter of SvO2 series
Test shift left and right
(C language) 3 small Codes: 1+2+3+ · · +100=? And judge whether a year is a leap year or a normal year? And calculate the circumference and area of the circle?
Go学习笔记—多线程
Experiment of connecting mobile phone hotspot based on Arduino and esp8266 (successful)
随机推荐
高德地图测试用例
PyTorch nn.RNN 参数全解析
MySQL indexes and transactions
Intel 内部指令 --- AVX和AVX2学习笔记
Find the factorial of a positive integer within 16, that is, the class of n (0= < n < =16). Enter 1111 to exit.
Fastdateformat why thread safe
Jenkins voucher management
Time format display
深入理解PyTorch中的nn.Embedding
WSL 2 will not be installed yet? It's enough to read this article
Jenkins用户权限管理
Leetcode122 the best time to buy and sell stocks II
Thesis translation: 2022_ PACDNN: A phase-aware composite deep neural network for speech enhancement
drools中then部分的写法
The blink code based on Arduino and esp8266 runs successfully (including error analysis)
(C language) 3 small Codes: 1+2+3+ · · +100=? And judge whether a year is a leap year or a normal year? And calculate the circumference and area of the circle?
Log4j2
SCM power supply
(C语言)输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。
Mish shake the new successor of the deep learning relu activation function