C++剑指offer（面试题68 - II. 二叉树的最近公共祖先）【递归】

糖逗

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

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



 

示例 1:

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

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

说明:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>

using namespace std;

struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(NULL), right(NULL){
        }
};

TreeNode* CreateTree(vector<int> input){
        TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size(); i++){
                res[i].val = input[i];
                res[i].left = NULL;
                res[i].right = NULL;
        }
        for(int i= 0; i < input.size(); i++){
                if(2*i+1 < input.size()){
                        res[i].left = &res[2*i+1];
                }
                if(2*i+2 < input.size()){
                        res[i].right = &res[2*i+2];
                }
                
        }
        return res;
        
}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
           
    middle(root->left, res, left, insert - 1, depth + 1);
    middle(root->right, res, insert + 1, right, depth + 1);
    }

int treeDepth(TreeNode* root){
    if(root == NULL) return 0;
    return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    }
      
void printTree(TreeNode* root) {
    int depth = treeDepth(root);
    int width = pow(2, depth) - 1;
    vector<vector<int> > res(depth, vector<int>(width, 0));
    middle(root, res, 0, width - 1, 0);
    for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                       
                }
                cout << endl;
        }
        cout << "------------------" << endl;
    }

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

TreeNode* solution(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == NULL) return NULL;
        if(root == p || root == q) return root;
        TreeNode* left = solution(root -> left, p, q);
        TreeNode* right = solution(root -> right, p, q);
        if(right && left) return root;
        return left ? left : right;
}

int main(void){
        vector<int> input;
        cout << "send numbers for the tree" << endl;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        cin.clear();
        cout << "send the first number" << endl;
        int first;
        cin >> first;
        cin.clear();
        TreeNode*root = CreateTree(input);
        printTree(root);
        TreeNode* firstNode = findNode(root, first, input);
        printTree(firstNode);
        
        cout << "send the second number" << endl;
        int second;
        cin >> second;
        TreeNode* secondNode = findNode(root, second, input);
        printTree(secondNode);
        
        
        TreeNode* res = solution(root, firstNode, secondNode);
        printTree(res);
        
        return 0;
}

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

糖逗

借鉴：https://fishc.com.cn/thread-163378-1-1.html中代码
新增代码：

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

TreeNode* solution(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == NULL) return NULL;
        if(root == p || root == q) return root;
        TreeNode* left = solution(root -> left, p, q);
        TreeNode* right = solution(root -> right, p, q);
        if(right && left) return root;
        return left ? left : right;
}

糖逗

最后的魁拔

求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢

糖逗

最后的魁拔 发表于 2020-4-2 14:40
求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢

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

糖逗

最后的魁拔 发表于 2020-4-2 14:40
求老哥,推荐一下c或者c++的数据结构的网课,。。。。 谢谢

我是自学的，非计算机科班。目前我是这么学的。

最后的魁拔

糖逗 发表于 2020-4-2 14:48
我是自学的，非计算机科班。目前我是这么学的。

老哥,请问一下,你大几了呢

最后的魁拔

糖逗 发表于 2020-4-2 14:48
我是自学的，非计算机科班。目前我是这么学的。

请问老哥,你学了哪几种语言呢？

乘号

最后的魁拔 发表于 2020-4-2 14:50
老哥,请问一下,你大几了呢

ta小学。。。

最后的魁拔

乘号 发表于 2020-4-10 08:28
ta小学。。。

只能说,这个论坛，小学生就太叼了