Day19-二叉树-最近公共祖先

BUPTrenyi

发布于 2019-07-15 17:01:42

8890

发布于 2019-07-15 17:01:42

文章被收录于专栏：算法其实很好玩

一唠嗑

需求紧，任务重，就不多废话了

回答一下后台小伙伴的问题：

Q：你用的什么IDE？

A：叫Clion。我很喜欢jetbrains家的IDE，我在用的有goland，pycharm，PHPstorm，intelliJ idea，包括现在用的Clion。

Q：命名函数为什么不用下划线？

A：公司里大部分都是驼峰式命名，比较规范，就形成个人习惯了，下划线也OK。

二上题！

Q：已知一个二叉树，给定两个节点，求这两个节点的最近公共祖先

举例：网上找一张图

5，0的最近公共祖先，就是3，根节点

5，4的最近公共祖先，就是5

7，4的最近公共祖先，就是2

三冷静分析

其实有了昨天的题，是做了很好的铺垫的。

逻辑比较简单，我直接说了啊

1.首先我们需要知道，两个节点的公共祖先，一定在，从根节点到这两个节点的路径上。

2.那么我们就先求出，从根节点到目标节点的路径（昨天求的是，从根节点到叶子节点的路径）。

3.路径长度并不一定相同。求出较小长度的路径长度，假定为n。那么同时遍历两个节点的路径，遍历n次，最后的相同的节点，即为最近公共节点。

举例：

节点7的路径：3 -> 5 -> 2 -> 7

节点4的路径：3 -> 5 -> 2 -> 4

长度一样，同时遍历两个路径，当发现最后的相同的节点，即2，就是最近公共祖先了

四完整代码及注释

//
// Created by renyi on 2019-07-04.
//
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : value(v), left(NULL), right(NULL){}
};

//建立函数，找到从根节点root到待搜索节点search的路径
void preOrder(TreeNode* root, TreeNode* search, vector<TreeNode*> &path, vector<TreeNode*> &result, int &finish){
    if (!root || finish){//用finish来标识是否找到了待搜索节点，以免不必要的递归
        return;
    }

    path.push_back(root);
    if (root == search){
        finish = 1;//找到了待搜索节点
        result = path;
    }
    preOrder(root->left, search, path, result, finish);
    preOrder(root->right, search, path, result, finish);
    path.pop_back();
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
    vector<TreeNode*> path;//临时路径栈
    vector<TreeNode*> pathP;//存储p，q节点的路径
    vector<TreeNode*> pathQ;
    int finish = 0;
    preOrder(root, p, path, pathP, finish);
    path.clear();//求完p节点的路径，把临时路径栈path清空
    finish = 0;
    preOrder(root, q, path, pathQ, finish);//再求q节点路径

    int pathLen = pathP.size() <= pathQ.size() ? pathP.size() : pathQ.size();//存储较短路径的长度

    TreeNode* result = nullptr;
    for (int i = 0; i < pathLen; i++) {
        if (pathP[i] == pathQ[i]){
            result = pathP[i];
        }
    }
    return result;
}

int main(){
    TreeNode a(3);//建立配图的二叉树
    TreeNode b(5);
    TreeNode c(1);
    TreeNode d(6);
    TreeNode e(2);
    TreeNode f(0);
    TreeNode g(8);
    TreeNode h(7);
    TreeNode i(4);

    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;
    c.right = &g;
    e.left = &h;
    e.right = &i;
    TreeNode* result = lowestCommonAncestor(&a, &b, &f);
    printf("%d ,%d 的最近公共祖先为: %d\n", b.value, f.value, result->value);

    result = lowestCommonAncestor(&a, &b, &i);
    printf("%d ,%d 的最近公共祖先为: %d\n", b.value, i.value, result->value);

    result = lowestCommonAncestor(&a, &h, &i);
    printf("%d ,%d 的最近公共祖先为: %d\n", h.value, i.value, result->value);

    return 0;
}

运行结果