本文实例讲述了C++实现寻找最低公共父节点的方法，是数据结构中二叉树的经典算法。分享给大家供大家参考。具体方法如下：
最低公共父节点，意思很好理解。
思路1：最低公共父节点满足这样的条件：两个节点分别位于其左子树和右子树，那么定义两个bool变量，leftFlag和rightFlag，如果在左子树中，leftFlag为true，如果在右子树中，rightFlag为true，仅当leftFlag == rightFlag == true时，才能满足条件。
实现代码如下：
#include
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft),
right(pRight) {}
Node *left;
Node *right;
int data;
};
Node *constructNode(Node **pNode1, Node **pNode2)
{
Node *node12 = new Node(12);
Node *node11 = new Node(11);
Node *node10 = new Node(10);
Node *node9 = new Node(9, NULL, node12);
Node *node8 = new Node(8, node11, NULL);
Node *node7 = new Node(7);
Node *node6 = new Node(6);
Node *node5 = new Node(5, node8, node9);
Node *node4 = new Node(4, node10);
Node *node3 = new Node(3, node6, node7);
Node *node2 = new Node(2, node4, node5);
Node *node1 = new Node(1, node2, node3);
*pNode1 = node6;
*pNode2 = node12;
return node1;
}
bool isNodeIn(Node *root, Node *node1, Node *node2)
{
if (node1 == NULL || node2 == NULL)
{
throw("invalid node1 and node2");
return false;
}
if (root == NULL)
return false;
if (root == node1 || root == node2)
{
return true;
}
else
{
return isNodeIn(root->left, node1, node2) || isNodeIn(root->right, node1, node2);
}
}
Node *lowestFarther(Node *root, Node *node1, Node *node2)
{
if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
{
return NULL;
}
bool leftFlag = false;
bool rightFlag = false;
leftFlag = isNodeIn(root->left, node1, node2);
rightFlag = isNodeIn(root->right, node1, node2);
if (leftFlag == true && rightFlag == true)
{
return root;
}
else if (leftFlag == true)
{
return lowestFarther(root->left, node1, node2);
}
else
{
return lowestFarther(root->right, node1, node2);
}
}
void main()
{
Node *node1 = NULL;
Node *node2 = NULL;
Node *root = constructNode(&node1, &node2);
cout