在二叉树中找到两个节点的最近公共祖先

[编程题]在二叉树中找到两个节点的最近公共祖先

热度指数：1790 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

最后一行为节点 o1 和 o2。

输出描述:

输出一个整数表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

typedef int Id;

typedef struct {
  Id id;
  Id l_child, r_child;
} TNodeInfo, *INFO;

int lowestCommonAncestor(INFO infos, Id root_id, Id p, Id q) {
  if (!root_id || root_id == p || root_id == q) return root_id;
  const int ls = lowestCommonAncestor(infos, (*(infos + root_id)).l_child, p, q);
  const int rs = lowestCommonAncestor(infos, (*(infos + root_id)).r_child, p, q);
  return ls && rs ? root_id : ls ? ls : rs;
}

int main(const int argc, const char** const argv) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  TNodeInfo infos[n + 1];
  Id fa, l_ch, r_ch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    (*(infos + fa)).id = fa;
    (*(infos + fa)).l_child = l_ch;
    (*(infos + fa)).r_child = r_ch;
  }
  
  Id o1, o2;
  fscanf(stdin, "%d %d", &o1, &o2);
  fprintf(stdout, "%d", lowestCommonAncestor(infos, root_id, o1, o2));
  return 0;
}

发表于 2021-07-31 19:29:58 回复(0)