专栏首页算法修养LeetCode 310. Minimum Height Trees (DFS)

LeetCode 310. Minimum Height Trees (DFS)

题目

给你一个无向无环图,这个图的任何一个节点都可以当成一个树的根节点。让你找到形成的树的高度最小的那几个根节点。

首先,这个根节点要么只有1个,要么只有2个。 而且就在图中最长的一条路径上,如果这个路径上的节点数为偶数,那就是2个,否则就是1个

那么怎么找这条最长路径呢?首先从任意 一个点出发,找到离它最远的点t1,然后从t1出发找到离它最远的点t2,t1和t2就是最长的路径上的两个端点

class Solution {
public:
    
vector<int> edge[100005];
int vis[100005];
int t1, t2;
int d1, d2;
int path[100005];
int pos;
int ans1, ans2;
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {

    vector<int> ans;
    if (edges.size() == 0)
        return ans;
    
    for(int i=0;i<n;i++)
    {
        v.push_back(edge);
    }
    for (int i = 0; i < edges.size(); i++)
    {
        edge[edges[i][0]].push_back(edges[i][1]);
        edge[edges[i][1]].push_back(edges[i][0]);
    }

    ans2 = -1;
    pos = 0;
    d1 = d2 = 0;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    DFS(0, 1);
    path[pos++] = t1;
    memset(vis,0,sizeof(vis));
    vis[t1]=1;
    DFS2(t1, 1);
    ans.push_back(ans1);
    if (ans2 != -1)
        ans.push_back(ans2);

    return ans;

}

void DFS(int node,int deep)
{
    if (d1 < deep)
    {
        d1 = deep;
        t1 = node;
    }
    for (int i = 0; i < edge[node].size(); i++)
    {
        if(vis[edge[node][i]])
            continue;
        vis[edge[node][i]]=1;
        DFS(edge[node][i], deep + 1);
    
    }
}

void DFS2(int node, int deep)
{
    
    if (d2 < deep)
    {
        if (pos & 1)
        {
            ans1 = path[pos / 2];
            ans2 = -1;
        }
        else
        {
            ans2 = path[pos / 2];
            ans1 = path[pos / 2 - 1];
        }
        d2 = deep;
    }

    for (int i = 0; i < edge[node].size(); i++)
    {
        if(vis[edge[node][i]])
            continue;
        vis[edge[node][i]]=1;
        path[pos++] = edge[node][i];
        DFS2(edge[node][i], deep + 1);
        pos--;
    }
}

};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法细节系列(19):广度搜索优先

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 0310 - Minimum Height Trees

    For an undirected graph with tree characteristics, we can choose any node as the...

    Reck Zhang
  • Golang Leetcode 310. Minimum Height Trees.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89068745

    anakinsun
  • leetcode310. Minimum Height Trees

    在无向图的生成树中,我们可以指定任何一个节点为这棵树的根节点。现在要求在这样一棵生成树中,找到生成树的高度最低的所有根节点。

    眯眯眼的猫头鹰
  • Leetcode 题目列表(难度、出现频率、知识点)

    不全,但好像没看到有更好的版本,刷前132题暂时凑合着用吧! 转载自:LeetCode Question Difficulty Distribution ?...

    triplebee
  • 二叉树问题(一)-LeetCode 110、617、101、814、655、98、654(递归思路)

    给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

    算法工程师之路
  • LeetCode Weekly Contest 46解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • BFS,丑数问题-LeetCode 310、264、313、328、343(拆分链表)

    对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找...

    算法工程师之路
  • LeetCode 872. 叶子相似的树

    请考虑一颗二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

    Michael阿明
  • 675. Cut Off Trees for Golf Event

    You are asked to cut off all the trees in this forest in the order of tree’s he...

    用户1147447
  • LeetCode Weekly Contest 43解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 865. 具有所有最深结点的最小子树(递归)

    返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

    Michael阿明
  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • LeetCode 96,n个数构建BST的方法有多少种?

    今天是LeetCode专题第62篇文章,我们一起来聊聊LeetCode的96题,Unique Binary Search Trees(唯一的二叉搜索树)。

    TechFlow-承志
  • 【Leetcode108】关关刷题日记65–Convert Sorted Array to Binary Search Tree

    关关的刷题日记65 – Leetcode 108. Convert Sorted Array to Binary Search Tree 题目 Given an...

    WZEARW
  • 算法细节系列(18):凸包的三种计算

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • leetcode 110 Balanced Binary Tree

    Balanced Binary Tree Total Accepted: 63288 Total Submissions: 198315 My Submiss...

    流川疯
  • LeetCode 94 | 构造出所有二叉搜索树

    今天是LeetCode专题第61篇文章,我们一起来看的是LeetCode95题,Unique Binary Search Trees II(不同的二叉搜索树II...

    TechFlow-承志

扫码关注云+社区

领取腾讯云代金券