王道-第五章 树与二叉树-代码练习

将一棵二叉树按顺序结构存储，求编号为i和j的两个结点的最近公共祖先节点的值

我首先想到了之前在力扣上写过的求二叉树中最近公共祖先的题目：(11条消息) 2021.10.9 力扣-二叉树的最近公共祖先_作用太大了销夜的博客-CSDN博客

于是按照这个思路写了出来：

node nodes[maxsize];
int length;    //二叉树的最后一个结点的编号
int findancestor(int cur, int i, int j)
{
    if (cur > length) return -1;
    if (cur == i || cur == j) return cur;
    int left = findancestor(2 * cur, i, j);
    int right = findancestor(2 * cur + 1, i, j);
    if (left != -1 && right != -1) return cur;
    else if (left != -1) return left;
    else return right;
    return -1;
}

但实际上用不着这么麻烦，因为这个二叉树是用顺序结构存储的，所以可以方便的使用公式找到某个结点的父结点。

思路是这样的：当i = j时就说明找到了i和j的最近公共祖先。假如i > j，那么就说明结点i位于结点j的同一层的右方，或者层数比j大，因此令i = i/2，将i转换为i的父结点，再继续循环判断，j > i时同理。

以下是书上所给的写法：

node nodes[maxsize];
int findancestor(int i, int j)
{
    //如果结点i和j都存在的话
    if (nodes[i].isexist && nodes[j].isexist)
    {
        while (i != j)
        {
            if (i > j)
            {
                i = i / 2;
            }
            else
            {
                j = j / 2;
            }
        }
        return nodes[i].value;
    }
    return -1;
}