C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法
本文實(shí)例講述了C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法,是數(shù)據(jù)結(jié)構(gòu)中二叉樹的經(jīng)典算法。分享給大家供大家參考。具體方法如下:
最低公共父節(jié)點(diǎn),意思很好理解。
思路1:最低公共父節(jié)點(diǎn)滿足這樣的條件:兩個(gè)節(jié)點(diǎn)分別位于其左子樹和右子樹,那么定義兩個(gè)bool變量,leftFlag和rightFlag,如果在左子樹中,leftFlag為true,如果在右子樹中,rightFlag為true,僅當(dāng)leftFlag == rightFlag == true時(shí),才能滿足條件。
實(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) {} 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; } }
這類問題在面試的時(shí)候常會遇到,對此需要考慮以下情形:
1. node1和node2指向同一節(jié)點(diǎn),這個(gè)如何處理
2. node1或node2有不為葉子節(jié)點(diǎn)的可能性嗎
3. node1或node2一定在樹中嗎
還要考慮一個(gè)效率問題,上述代碼中用了兩個(gè)遞歸函數(shù),而且存在不必要的遞歸過程,仔細(xì)思考,其實(shí)一個(gè)遞歸過程足以解決此問題
實(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è)計(jì)的學(xué)習(xí)有所幫助。
相關(guān)文章
應(yīng)用程序操作NorFlash示例代碼分享(norflash接口使用方法)
相對于操作NandFlash,操作NorFlash相對簡單,因?yàn)榛静恍枰紤]壞塊,NorFlash也沒有OOB區(qū)域,也跟ECC沒有關(guān)系。讀寫擦除相對容易,下面看個(gè)例子吧2013-12-12C++中的動(dòng)態(tài)分派在HotSpot?VM中的應(yīng)用小結(jié)
多態(tài)是面向?qū)ο缶幊陶Z言的重要特性,它允許基類的指針或引用指向派生類的對象,而在具體訪問時(shí)實(shí)現(xiàn)方法的動(dòng)態(tài)綁定,這篇文章主要介紹了C++的動(dòng)態(tài)分派在HotSpot?VM中的重要應(yīng)用,需要的朋友可以參考下2023-09-09C語言基礎(chǔ)知識點(diǎn)解析(extern,static,typedef,const)
本篇文章是對C語言基礎(chǔ)知識點(diǎn)(extern,static,typedef,const)的用法進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過來參考下2013-10-10C++詳細(xì)講解互斥量與lock_guard類模板及死鎖
線程的主要優(yōu)勢在于,能夠通過全局變量來共享信息。不過,這種便捷的共享是有代價(jià)的:必須確保多個(gè)線程不會同時(shí)修改同一變量,或者某一線程不會讀取正由其他線程修改的變量。為了防止出現(xiàn)線程某甲試圖訪 問一共享變量時(shí),線程某乙正在對其進(jìn)行修改。引入了互斥量2022-07-07C語言實(shí)現(xiàn)文件內(nèi)容按行隨機(jī)排列的算法示例
這篇文章主要介紹了C語言實(shí)現(xiàn)文件內(nèi)容按行隨機(jī)排列的算法,涉及C語言字符串、數(shù)組遍歷與隨機(jī)數(shù)相關(guān)算法實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-09-09解析VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類的深入分析
本篇文章是對VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05