经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
漫画讲解C语言中最近公共祖先的三种类型
来源:jb51  时间:2021/11/24 11:07:51  对本文有异议

在这里插入图片描述

在这里插入图片描述

最近公共祖先定义

在这里插入图片描述

在这里插入图片描述

查找最近公共祖先

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

三叉链

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下:

  1. //三叉链
  2. struct TreeNode {
  3. int val;
  4. TreeNode *left;
  5. TreeNode *right;
  6. TreeNode *parent;
  7. TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
  8. };
  9. class Solution {
  10. public:
  11. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  12. TreeNode* curp = p, *curq = q; //用于遍历p、q结点的祖先结点
  13. int lenp = 0, lenq = 0; //分别记录p、q结点各自的祖先结点个数
  14. //统计p结点的祖先结点个数
  15. while (curp != root)
  16. {
  17. lenp++;
  18. curp = curp->parent;
  19. }
  20. //统计q结点的祖先结点个数
  21. while (curq != root)
  22. {
  23. lenq++;
  24. curq = curq->parent;
  25. }
  26. //longpath和shortpath分别标记祖先路径较长和较短的结点
  27. TreeNode* longpath = p, *shortpath = q;
  28. if (lenp < lenq)
  29. {
  30. longpath = q;
  31. shortpath = p;
  32. }
  33. //p、q结点祖先结点个数的差值
  34. int count = abs(lenp - lenq);
  35. //先让longpath往上走count个结点
  36. while (count--)
  37. {
  38. longpath = longpath->parent;
  39. }
  40. //再让longpath和shortpath同时往上走,此时第一个相同的结点便是最近公共祖先结点
  41. while (longpath != shortpath)
  42. {
  43. longpath = longpath->parent;
  44. shortpath = shortpath->parent;
  45. }
  46. return longpath; //返回最近公共祖先结点
  47. }
  48. };

二叉搜索树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下:

  1. //搜索二叉树
  2. struct TreeNode {
  3. int val;
  4. TreeNode *left;
  5. TreeNode *right;
  6. TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  7. };
  8. class Solution {
  9. public:
  10. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  11. if (p->val == root->val || q->val == root->val) //p、q结点中某一个结点的值等于根结点的值,则根结点就是这两个结点的最近公共祖先
  12. return root;
  13. if (p->val < root->val&&q->val < root->val) //p、q结点的值都小于根结点的值,说明这两个结点的最近公共祖先在该树的左子树当中
  14. return lowestCommonAncestor(root->left, p, q);
  15. else if (p->val > root->val&&q->val > root->val) //p、q结点的值都大于根结点的值,说明这两个结点的最近公共祖先在该树的右子树当中
  16. return lowestCommonAncestor(root->right, p, q);
  17. else //p、q结点的值一个比根小一个比根大,说明根就是这两个结点的最近公共祖先
  18. return root;
  19. }
  20. };

普通二叉树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下:

  1. //普通二叉树
  2. struct TreeNode {
  3. int val;
  4. TreeNode *left;
  5. TreeNode *right;
  6. TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  7. };
  8. class Solution {
  9. public:
  10. bool Find(TreeNode* root, TreeNode* x)
  11. {
  12. if (root == nullptr) //空树,查找失败
  13. return false;
  14. if (root == x) //查找成功
  15. return true;
  16.  
  17. return Find(root->left, x) || Find(root->right, x); //在左子树找到了或是右子树找到了,都说明该结点在该树当中
  18. }
  19. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  20. if (p == root || q == root) //p、q结点中某一个结点为根结点,则根结点就是这两个结点的最近公共祖先
  21. return root;
  22. //判断p、q结点是否在左右子树
  23. bool IspInLeft, IspInRight, IsqInLeft, IsqInRight;
  24. IspInLeft = Find(root->left, p);
  25. IspInRight = !IspInLeft;
  26. IsqInLeft = Find(root->left, q);
  27. IsqInRight = !IsqInLeft;
  28.  
  29. if (IspInLeft&&IsqInLeft) //p、q结点都在左子树,说明这两个结点的最近公共祖先也在左子树当中
  30. return lowestCommonAncestor(root->left, p, q);
  31. else if (IspInRight&&IsqInRight) //p、q结点都在右子树,说明这两个结点的最近公共祖先也在右子树当中
  32. return lowestCommonAncestor(root->right, p, q);
  33. else //p、q结点一个在左子树一个在右子树,说明根就是这两个结点的最近公共祖先
  34. return root;
  35. }
  36. };

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

看着似乎不太好理解,来看看下面的动图演示:

在这里插入图片描述

代码如下:

  1. //普通二叉树
  2. struct TreeNode {
  3. int val;
  4. TreeNode *left;
  5. TreeNode *right;
  6. TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  7. };
  8. class Solution {
  9. public:
  10. bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
  11. {
  12. if (root == nullptr)
  13. return false;
  14. path.push(root); //该结点可能是路径当中的结点,先入栈
  15.  
  16. if (root == x) //该结点是最终结点,查找结束
  17. return true;
  18.  
  19. if (FindPath(root->left, x, path)) //在该结点的左子树找到了最终结点,查找结束
  20. return true;
  21. if (FindPath(root->right, x, path)) //在该结点的右子树找到了最终结点,查找结束
  22. return true;
  23.  
  24. path.pop(); //在该结点的左右子树均没有找到最终结点,该结点不可能是路径当中的结点,该结点出栈
  25. return false; //在该结点处查找失败
  26. }
  27. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  28. stack<TreeNode*> pPath, qPath;
  29. FindPath(root, p, pPath); //将从根到p结点的路径存放到pPath当中
  30. FindPath(root, q, qPath); //将从根到q结点的路径存放到qPath当中
  31. //longpath和shortpath分别标记长路径和短路径
  32. stack<TreeNode*>* longPath = &pPath, *shortPath = &qPath;
  33. if (pPath.size() < qPath.size())
  34. {
  35. longPath = &qPath;
  36. shortPath = &pPath;
  37. }
  38. //让longPath先弹出差值个数据
  39. int count = longPath->size() - shortPath->size();
  40. while (count--)
  41. {
  42. longPath->pop();
  43. }
  44. //longPath和shortPath一起弹数据,直到两个栈顶的结点相同
  45. while (longPath->top() != shortPath->top())
  46. {
  47. longPath->pop();
  48. shortPath->pop();
  49. }
  50. return longPath->top(); //返回这个相同的结点,即最近公共祖先
  51. }
  52. };

在这里插入图片描述

到此这篇关于漫画讲解C语言中最近公共祖先的三种类型的文章就介绍到这了,更多相关C语言 公共祖先内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号