漫畫講解C語言中最近公共祖先的三種類型
最近公共祖先定義
查找最近公共祖先
三叉鏈
代碼如下:
//三叉鏈 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode *parent; TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {} }; class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* curp = p, *curq = q; //用於遍歷p、q結點的祖先結點 int lenp = 0, lenq = 0; //分別記錄p、q結點各自的祖先結點個數 //統計p結點的祖先結點個數 while (curp != root) { lenp++; curp = curp->parent; } //統計q結點的祖先結點個數 while (curq != root) { lenq++; curq = curq->parent; } //longpath和shortpath分別標記祖先路徑較長和較短的結點 TreeNode* longpath = p, *shortpath = q; if (lenp < lenq) { longpath = q; shortpath = p; } //p、q結點祖先結點個數的差值 int count = abs(lenp - lenq); //先讓longpath往上走count個結點 while (count--) { longpath = longpath->parent; } //再讓longpath和shortpath同時往上走,此時第一個相同的結點便是最近公共祖先結點 while (longpath != shortpath) { longpath = longpath->parent; shortpath = shortpath->parent; } return longpath; //返回最近公共祖先結點 } };
二叉搜索樹
代碼如下:
//搜索二叉樹 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val == root->val || q->val == root->val) //p、q結點中某一個結點的值等於根結點的值,則根結點就是這兩個結點的最近公共祖先 return root; if (p->val < root->val&&q->val < root->val) //p、q結點的值都小於根結點的值,說明這兩個結點的最近公共祖先在該樹的左子樹當中 return lowestCommonAncestor(root->left, p, q); else if (p->val > root->val&&q->val > root->val) //p、q結點的值都大於根結點的值,說明這兩個結點的最近公共祖先在該樹的右子樹當中 return lowestCommonAncestor(root->right, p, q); else //p、q結點的值一個比根小一個比根大,說明根就是這兩個結點的最近公共祖先 return root; } };
普通二叉樹
代碼如下:
//普通二叉樹 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: bool Find(TreeNode* root, TreeNode* x) { if (root == nullptr) //空樹,查找失敗 return false; if (root == x) //查找成功 return true; return Find(root->left, x) || Find(root->right, x); //在左子樹找到瞭或是右子樹找到瞭,都說明該結點在該樹當中 } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p == root || q == root) //p、q結點中某一個結點為根結點,則根結點就是這兩個結點的最近公共祖先 return root; //判斷p、q結點是否在左右子樹 bool IspInLeft, IspInRight, IsqInLeft, IsqInRight; IspInLeft = Find(root->left, p); IspInRight = !IspInLeft; IsqInLeft = Find(root->left, q); IsqInRight = !IsqInLeft; if (IspInLeft&&IsqInLeft) //p、q結點都在左子樹,說明這兩個結點的最近公共祖先也在左子樹當中 return lowestCommonAncestor(root->left, p, q); else if (IspInRight&&IsqInRight) //p、q結點都在右子樹,說明這兩個結點的最近公共祖先也在右子樹當中 return lowestCommonAncestor(root->right, p, q); else //p、q結點一個在左子樹一個在右子樹,說明根就是這兩個結點的最近公共祖先 return root; } };
看著似乎不太好理解,來看看下面的動圖演示:
代碼如下:
//普通二叉樹 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) { if (root == nullptr) return false; path.push(root); //該結點可能是路徑當中的結點,先入棧 if (root == x) //該結點是最終結點,查找結束 return true; if (FindPath(root->left, x, path)) //在該結點的左子樹找到瞭最終結點,查找結束 return true; if (FindPath(root->right, x, path)) //在該結點的右子樹找到瞭最終結點,查找結束 return true; path.pop(); //在該結點的左右子樹均沒有找到最終結點,該結點不可能是路徑當中的結點,該結點出棧 return false; //在該結點處查找失敗 } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> pPath, qPath; FindPath(root, p, pPath); //將從根到p結點的路徑存放到pPath當中 FindPath(root, q, qPath); //將從根到q結點的路徑存放到qPath當中 //longpath和shortpath分別標記長路徑和短路徑 stack<TreeNode*>* longPath = &pPath, *shortPath = &qPath; if (pPath.size() < qPath.size()) { longPath = &qPath; shortPath = &pPath; } //讓longPath先彈出差值個數據 int count = longPath->size() - shortPath->size(); while (count--) { longPath->pop(); } //longPath和shortPath一起彈數據,直到兩個棧頂的結點相同 while (longPath->top() != shortPath->top()) { longPath->pop(); shortPath->pop(); } return longPath->top(); //返回這個相同的結點,即最近公共祖先 } };
到此這篇關於漫畫講解C語言中最近公共祖先的三種類型的文章就介紹到這瞭,更多相關C語言 公共祖先內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!