C++實現(xiàn)尋找最低公共父節(jié)點的方法
更新時間：2014年09月18日 09:53:08 投稿：shichen2014
這篇文章主要介紹了C++實現(xiàn)尋找最低公共父節(jié)點的方法,是數(shù)據(jù)結(jié)構(gòu)中二叉樹的一個經(jīng)典算法,有一定的借鑒價值,需要的朋友可以參考下
本文實例講述了C++實現(xiàn)尋找最低公共父節(jié)點的方法，是數(shù)據(jù)結(jié)構(gòu)中二叉樹的經(jīng)典算法。分享給大家供大家參考。具體方法如下：
最低公共父節(jié)點，意思很好理解。
思路1：最低公共父節(jié)點滿足這樣的條件：兩個節(jié)點分別位于其左子樹和右子樹，那么定義兩個bool變量，leftFlag和rightFlag，如果在左子樹中，leftFlag為true，如果在右子樹中，rightFlag為true，僅當(dāng)leftFlag == rightFlag == true時，才能滿足條件。
實現(xiàn)代碼如下：
#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指向同一節(jié)點，這個如何處理
2. node1或node2有不為葉子節(jié)點的可能性嗎
3. node1或node2一定在樹中嗎
還要考慮一個效率問題，上述代碼中用了兩個遞歸函數(shù)，而且存在不必要的遞歸過程，仔細思考，其實一個遞歸過程足以解決此問題
實現(xiàn)代碼如下：
#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++程序算法設(shè)計的學(xué)習(xí)有所幫助。
相關(guān)文章
應(yīng)用程序操作NorFlash示例代碼分享(norflash接口使用方法)
相對于操作NandFlash，操作NorFlash相對簡單，因為基本不需要考慮壞塊，NorFlash也沒有OOB區(qū)域，也跟ECC沒有關(guān)系。讀寫擦除相對容易,下面看個例子吧2013-12-12
C++中的動態(tài)分派在HotSpot?VM中的應(yīng)用小結(jié)
多態(tài)是面向?qū)ο缶幊陶Z言的重要特性，它允許基類的指針或引用指向派生類的對象，而在具體訪問時實現(xiàn)方法的動態(tài)綁定，這篇文章主要介紹了C++的動態(tài)分派在HotSpot?VM中的重要應(yīng)用,需要的朋友可以參考下2023-09-09
C語言基礎(chǔ)知識點解析(extern,static,typedef,const)
本篇文章是對C語言基礎(chǔ)知識點(extern,static,typedef,const)的用法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-10-10
線程的主要優(yōu)勢在于，能夠通過全局變量來共享信息。不過，這種便捷的共享是有代價的：必須確保多個線程不會同時修改同一變量，或者某一線程不會讀取正由其他線程修改的變量。為了防止出現(xiàn)線程某甲試圖訪 問一共享變量時，線程某乙正在對其進行修改。引入了互斥量2022-07-07
有時候需要類的一些成員與類本身相關(guān)聯(lián)，而不是與類的每個對象相關(guān)聯(lián)。比如類的所有對象都要共享的變量，這個時候我們就要用到類的靜態(tài)成員，今天通過實例代碼給大家詳細介紹，需要的朋友參考下吧2021-07-07
這篇文章主要介紹了C語言輸出唯一的子串，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-12-12
C語言實現(xiàn)文件內(nèi)容按行隨機排列的算法示例
這篇文章主要介紹了C語言實現(xiàn)文件內(nèi)容按行隨機排列的算法,涉及C語言字符串、數(shù)組遍歷與隨機數(shù)相關(guān)算法實現(xiàn)技巧,需要的朋友可以參考下2017-09-09
這篇文章主要為大家詳細介紹了Qt實現(xiàn)簡單五子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
解析VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類的深入分析
本篇文章是對VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++中的數(shù)組、鏈表與哈希表，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09