DP in C++


  • 0
    D

    I implement the dynamic programming idea described in another post. Although the implementation in lengthy, that is an interesting idea for me.

        v
     /  |  \
    0   u   0
      / | \
     0  0  0
    (0 denotes a subtree)
    

    The key observation is the recursive formula:
    height of tree at u = max(longest path of graph ending at u but not in the subtree of u, longest path in subtree of u)
    where
    the longest path of graph ending at u but not in the subtree of u = longest or second longest path at parent v + 1 (one edge v->u)

    Time: O(n) because each node is visited 2 times, space : O(n) for the arrays

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n == 1)
                return vector<int> (1, 0);
            vector<vector<int>> graph(n);
            for (pair<int, int> edge : edges) {
                graph[edge.first].emplace_back(edge.second);
                graph[edge.second].emplace_back(edge.first);
            }
            
            vector<int> longest(n), s_longest(n);
            findLongestPathsFrom(0, -1, longest, s_longest, graph);
    
            
            vector<int> heights(n);
            findHeightsFrom(0, -1, 1, heights, longest, s_longest, graph);
    
            vector<int> result;
            int min_h = n;
            for (int i = 0; i < n; ++i) {
                if (min_h >= heights[i]) {
                    if (heights[i] < min_h) {
                        min_h = heights[i];
                        result.clear();
                    }   
                    result.emplace_back(i);
                }
            }
            return result;
        }
        
        void findLongestPathsFrom(int root, int parent, vector<int>& longest, vector<int>& s_longest, const vector<vector<int>>& graph) {
            longest[root] = 1;
            s_longest[root] = 1;
    
            for (int child : graph[root]) {
                if (child == parent)
                    continue;
                findLongestPathsFrom(child, root, longest, s_longest, graph);
                
                int tmp = longest[child] + 1;
                if (tmp > longest[root]) {
                    s_longest[root] = longest[root];
                    longest[root] = longest[child] + 1;
                } else if (tmp > s_longest[root]) {
                    s_longest[root] = longest[child] + 1;
                }
            }
        }
        
        void findHeightsFrom(int root, int parent, int upper_longest, vector<int>& heights, const vector<int>& longest, const vector<int>& s_longest, const vector<vector<int>>& graph) {
            heights[root] = max(upper_longest, longest[root]);
            for (int child : graph[root]) {
                if (child == parent)
                    continue;
                
                int child_upper_longest = max(upper_longest, longest[child] + 1 == longest[root] ? s_longest[root]: longest[root]);
                
                findHeightsFrom(child, root, child_upper_longest + 1, heights, longest, s_longest, graph);
            }
        }
    
    };
    

Log in to reply
 

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