C++实现二叉树最低公共父节点的经典算法详解

在C++中，寻找最低公共父节点（Lowest Common Ancestor，LCA）是二叉树中常见的一个算法问题，主要用于查找两个给定节点在树中的最近公共祖先节点。这个任务可以通过递归或者迭代的方式实现，本文主要讲解一种基于递归的思路。 首先，我们定义一个二叉树节点结构，包含整型数据`data`，以及指向左右子节点的指针`left`和`right`。在C++中，我们用`Node`结构体表示节点，并通过`Node`构造函数初始化它们的值和子节点。 思路1的核心在于判断两个节点是否都在各自节点的左子树或右子树中。为此，我们创建了两个布尔变量`leftFlag`和`rightFlag`，初始时都设置为`false`。当遍历到某个节点时，如果它在当前节点的左子树，`leftFlag`置为`true`；如果在右子树，则`rightFlag`置为`true`。如果这两个标志同时为`true`，则说明当前节点是两个给定节点的共同祖先，但不一定是最低的，我们需要继续向上查找，直到找到`leftFlag`和`rightFlag`同时为`true`的最近节点。 为了演示这个方法，文章提供了一个`constructNode`函数，用于构建一个具有特定节点关系的示例二叉树。这个函数创建了一个示例树结构，方便后续查找操作。 `isNodeIn`函数则是实际的查找功能，它接收三个参数：根节点`root`，待查找的节点`node1`和`node2`。函数首先检查输入节点是否有效，然后递归地比较每个节点及其子节点，直到找到满足条件的公共祖先。当`node1`或`node2`为`NULL`时，函数返回`false`，否则，如果`leftFlag`和`rightFlag`同时为`true`，则说明找到了公共祖先，返回`true`，并停止递归。 C++实现寻找最低公共父节点的方法利用了二叉树的特性，通过递归检查节点的位置来确定共同祖先，当遇到公共祖先且满足左右子树条件时，即找到最低公共父节点。这种方法适用于任何二叉树结构，并在数据结构和算法课程中具有实际应用价值。