C++ O(n) 36ms Beats 94%, Two DFS and Done. Quick and Clean


  • 0
    F
    class Solution {
        int depth = 0, deepest_node = -1;
        vector<vector<int>> tree;
        vector<int> result;
        void buildTree(vector<pair<int, int>>& edges)
        {
            for (auto & e : edges)
            {
                tree[e.first].push_back(e.second);
                tree[e.second].push_back(e.first);
            }
        }
        void dfs(vector<int> & path)
        {
            int node = path.back(), parent = path[path.size() - 2];
            if (tree[node].empty() || (tree[node].size() == 1 && tree[node][0] == parent))
            {
                if (path.size() > depth)
                {
                    depth = path.size();
                    deepest_node = node;
                    result.clear(); 
                    if (path.size() % 2 == 1)
                        result.push_back(path[path.size() / 2 + 1]);
                    result.push_back(path[path.size() / 2 ]);
                }
                return;
            }
            for (int n : tree[node])
                if (n != parent)
                {
                    path.push_back(n);
                    dfs(path);
                    path.pop_back();
                }
        }
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            tree.resize(n);
            buildTree(edges);
            vector<int> path{-1, 0};
            dfs(path);
            path.back() = deepest_node;
            dfs(path);
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.