leetcode::minimum_height_trees::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static int	findLongestNode (int u, vector< int > &parent, vector< vector< int > > &adj)
static vector< int >	findMinHeightTrees (int n, vector< vector< int > > &edges)

详细描述

在文件 leetcode.h 第 2125 行定义.

成员函数说明

findLongestNode()

int leetcode::minimum_height_trees::Solution::findLongestNode ( int  u, vector< int > &  parent, vector< vector< int > > &  adj  )

static

在文件 leetcode.cpp 第 5765 行定义.

                                                                                          {
            const int n = adj.size();
            queue<int> qu;
            vector<bool> visit(n);
            qu.emplace(u);
            visit[u] = true;
            int node = -1;
 
            while(!qu.empty()) {
                const int curr = qu.front();
                qu.pop();
                node = curr;
                for(auto &v: adj[curr]) {
                    if(!visit[v]) {
                        visit[v]  = true;
                        parent[v] = curr;
                        qu.emplace(v);
                    }
                }
            }
            return node;
        }

被这些函数引用 findMinHeightTrees().

findMinHeightTrees()

vector< int > leetcode::minimum_height_trees::Solution::findMinHeightTrees ( int  n, vector< vector< int > > &  edges  )

static

在文件 leetcode.cpp 第 5736 行定义.

                                                                                  {
            if(n == 1) {
                return {0};
            }
            vector<vector<int>> adj(n);
            for(auto &edge: edges) {
                adj[edge[0]].emplace_back(edge[1]);
                adj[edge[1]].emplace_back(edge[0]);
            }
 
            vector parent(n, -1);
            /* 找到与节点 0 最远的节点 x */
            const int x = findLongestNode(0, parent, adj);
            /* 找到与节点 x 最远的节点 y */
            int y = findLongestNode(x, parent, adj);
            /* 求出节点 x 到节点 y 的路径 */
            vector<int> path;
            parent[x] = -1;
            while(y != -1) {
                path.emplace_back(y);
                y = parent[y];
            }
            const int m = path.size();
            if(m % 2 == 0) {
                return {path[m / 2 - 1], path[m / 2]};
            }
            return {path[m / 2]};
        }

引用了 findLongestNode().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp