鱼C论坛

 找回密码
 立即注册
查看: 802|回复: 9

[技术交流] C++剑指offer(面试题68 - II. 二叉树的最近公共祖先)【递归】

[复制链接]
发表于 2020-4-2 14:33:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-5-8 18:05 编辑

题目描述:
  1. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

  2. 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

  3. 例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]



  4.  

  5. 示例 1:

  6. 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  7. 输出: 3
  8. 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
  9. 示例 2:

  10. 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  11. 输出: 5
  12. 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
  13.  

  14. 说明:

  15. 所有节点的值都是唯一的。
  16. p、q 为不同节点且均存在于给定的二叉树中。

  17. 来源:力扣(LeetCode)
  18. 链接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
  19. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码



  1. #include<iostream>
  2. #include <malloc.h>
  3. #include <vector>
  4. #include <math.h>

  5. using namespace std;

  6. struct TreeNode{
  7.         int val;
  8.         TreeNode* left;
  9.         TreeNode* right;
  10.         TreeNode(int x): val(x), left(NULL), right(NULL){
  11.         }
  12. };

  13. TreeNode* CreateTree(vector<int> input){
  14.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
  15.         for(int i = 0; i < input.size(); i++){
  16.                 res[i].val = input[i];
  17.                 res[i].left = NULL;
  18.                 res[i].right = NULL;
  19.         }
  20.         for(int i= 0; i < input.size(); i++){
  21.                 if(2*i+1 < input.size()){
  22.                         res[i].left = &res[2*i+1];
  23.                 }
  24.                 if(2*i+2 < input.size()){
  25.                         res[i].right = &res[2*i+2];
  26.                 }
  27.                
  28.         }
  29.         return res;
  30.        
  31. }

  32. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
  33.     if(root == NULL) return;
  34.     int insert = left + (right - left) / 2;
  35.     res[depth][insert] = root->val;
  36.            
  37.     middle(root->left, res, left, insert - 1, depth + 1);
  38.     middle(root->right, res, insert + 1, right, depth + 1);
  39.     }

  40. int treeDepth(TreeNode* root){
  41.     if(root == NULL) return 0;
  42.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
  43.     }
  44.       
  45. void printTree(TreeNode* root) {
  46.     int depth = treeDepth(root);
  47.     int width = pow(2, depth) - 1;
  48.     vector<vector<int> > res(depth, vector<int>(width, 0));
  49.     middle(root, res, 0, width - 1, 0);
  50.     for(int i = 0; i < res.size(); i++){
  51.                 for(int j = 0; j < res[i].size();j++){
  52.                         if(res[i][j] == 0){
  53.                                 cout  << " ";
  54.                         }
  55.                         else{
  56.                                 cout << res[i][j];
  57.                         }
  58.                        
  59.                 }
  60.                 cout << endl;
  61.         }
  62.         cout << "------------------" << endl;
  63.     }

  64. TreeNode* findNode(TreeNode* root, int number, vector<int> input){
  65.         for(int i = 0; i < input.size(); i++){
  66.                 if(root[i].val == number) return &root[i];
  67.         }
  68.         return NULL;
  69. }

  70. TreeNode* solution(TreeNode* root, TreeNode* p, TreeNode* q){
  71.         if(root == NULL) return NULL;
  72.         if(root == p || root == q) return root;
  73.         TreeNode* left = solution(root -> left, p, q);
  74.         TreeNode* right = solution(root -> right, p, q);
  75.         if(right && left) return root;
  76.         return left ? left : right;
  77. }

  78. int main(void){
  79.         vector<int> input;
  80.         cout << "send numbers for the tree" << endl;
  81.         int number;
  82.         while(cin >> number){
  83.                 input.push_back(number);
  84.         }
  85.         cin.clear();
  86.         cout << "send the first number" << endl;
  87.         int first;
  88.         cin >> first;
  89.         cin.clear();
  90.         TreeNode*root = CreateTree(input);
  91.         printTree(root);
  92.         TreeNode* firstNode = findNode(root, first, input);
  93.         printTree(firstNode);
  94.        
  95.         cout << "send the second number" << endl;
  96.         int second;
  97.         cin >> second;
  98.         TreeNode* secondNode = findNode(root, second, input);
  99.         printTree(secondNode);
  100.        
  101.        
  102.         TreeNode* res = solution(root, firstNode, secondNode);
  103.         printTree(res);
  104.        
  105.         return 0;
  106. }
复制代码


注意事项:
1.参考链接:https://leetcode-cn.com/problems ... -wen-ti-by-walkerr/
2.有可能搜索的两个数的公共根是其中一个数。

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-4-2 14:34:06 | 显示全部楼层
借鉴:https://fishc.com.cn/thread-163378-1-1.html中代码
新增代码:
  1. TreeNode* findNode(TreeNode* root, int number, vector<int> input){
  2.         for(int i = 0; i < input.size(); i++){
  3.                 if(root[i].val == number) return &root[i];
  4.         }
  5.         return NULL;
  6. }

  7. TreeNode* solution(TreeNode* root, TreeNode* p, TreeNode* q){
  8.         if(root == NULL) return NULL;
  9.         if(root == p || root == q) return root;
  10.         TreeNode* left = solution(root -> left, p, q);
  11.         TreeNode* right = solution(root -> right, p, q);
  12.         if(right && left) return root;
  13.         return left ? left : right;
  14. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-2 14:34:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-4-2 14:40:32 | 显示全部楼层
求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-2 14:47:45 | 显示全部楼层
最后的魁拔 发表于 2020-4-2 14:40
求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢

微博有一个算法时空的博主他推 数据结构与算法 和极简数据结构(主讲C++)。我听过这两个课,但这个都是纯讲理论的实操少,刚入门学起来比较费劲。建议还是刷leetcode,对应着问题去看算法。比如说这道题涉及到动态规划,那你就可以去bilibili上搜动态规划看动态规划的原理,再对应做题。可能前期刷leetcode有些题不能自己想出来,但没关系边练边看算法一点点就好了。数据结构还是要多动手,只看网课不动手效果不大,进步不明显。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-2 14:48:34 | 显示全部楼层
最后的魁拔 发表于 2020-4-2 14:40
求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢

我是自学的,非计算机科班。目前我是这么学的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-2 14:50:50 | 显示全部楼层
糖逗 发表于 2020-4-2 14:48
我是自学的,非计算机科班。目前我是这么学的。

老哥,请问一下,你大几了呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-2 14:53:48 | 显示全部楼层
糖逗 发表于 2020-4-2 14:48
我是自学的,非计算机科班。目前我是这么学的。

请问老哥,你学了哪几种语言呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-10 08:28:41 | 显示全部楼层
最后的魁拔 发表于 2020-4-2 14:50
老哥,请问一下,你大几了呢

ta小学。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-10 08:47:58 | 显示全部楼层


只能说,这个论坛,小学生就太叼了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 16:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表