C++完成尋覓最低公共父節點的辦法

C++完成尋覓最低公共父節點的辦法。本站提示廣大學習愛好者：（C++完成尋覓最低公共父節點的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成尋覓最低公共父節點的辦法正文

本文實例講述了C++完成尋覓最低公共父節點的辦法，是數據構造中二叉樹的經典算法。分享給年夜家供年夜家參考。詳細辦法以下：

最低公共父節點，意思很好懂得。

思緒1：最低公共父節點知足如許的前提：兩個節點分離位於其左子樹和右子樹，那末界說兩個bool變量，leftFlag和rightFlag，假如在左子樹中，leftFlag為true，假如在右子樹中，rightFlag為true，僅當leftFlag == rightFlag == true時，能力知足前提。

完成代碼以下：

#include <iostream>

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 << "node1: " << node1->data << endl;
 cout << "node2: " << node2->data << endl;
 cout << "root: " << root->data << endl;

 Node *father = lowestFarther(root, node1, node2);

 if (father == NULL)
 {
 cout << "no common father" << endl;
 }
 else
 {
 cout << "father: " << father->data << endl;
 }
}

這類成績在面試的時刻常會碰到，對此須要斟酌以下情況：

1. node1和node2指向統一節點，這個若何處置
2. node1或node2有不為葉子節點的能夠性嗎
3. node1或node2必定在樹中嗎

還要斟酌一個效力成績，上述代碼頂用了兩個遞歸函數，並且存在不用要的遞歸進程，細心思慮，其實一個遞歸進程足以處理此成績

完成代碼以下：

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

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 = node5; 

 return node1; 
}

bool lowestFather(Node *root, Node *node1, Node *node2, Node *&dest)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return false;
 if (root == node1 || root == node2)
 return true;

 bool leftFlag = lowestFather(root->left, node1, node2, dest);
 bool rightFlag = lowestFather(root->right, node1, node2, dest);
 
 if (leftFlag == true && rightFlag == true)
 {
 dest = root;
 }
 if (leftFlag == true || rightFlag == true)
 return true;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 bool flag = lowestFather(root, node1, node2, dest);

 if (dest != NULL)
 {
 cout << "lowest common father: " << dest->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

上面再換一種方法的寫法以下：

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

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 = node11; 
 *pNode2 = node12; 

 return node1; 
}

Node* lowestFather(Node *root, Node *node1, Node *node2)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return NULL;
 if (root == node1 || root == node2)
 return root;

 Node* leftFlag = lowestFather(root->left, node1, node2);
 Node* rightFlag = lowestFather(root->right, node1, node2);

 if (leftFlag == NULL)
 return rightFlag;
 else if (rightFlag == NULL)
 return leftFlag;
 else
 return root;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 Node* flag = lowestFather(root, node1, node2);

 if (flag != NULL)
 {
 cout << "lowest common father: " << flag->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

願望本文所述對年夜家C++法式算法設計的進修有所贊助。