C++ Graph Solution


  • 0

    Leaf node's out degree is 0.
    Like remove outsize notes of graph.
    Not simple as counting heights but still O(n) time and space

    class Solution {
        void helper(TreeNode* cur) {
            if (!cur)
                return;
            if (cur->left) {
                graph[cur->left] = cur;
                outdegree[cur]++;
            }
            if (cur->right) {
                graph[cur->right] = cur;
                outdegree[cur]++;
            }
            if (!cur->left && !cur->right)
                outdegree[cur] = 0;
            helper(cur->left);
            helper(cur->right);
        }
        unordered_map<TreeNode*, TreeNode*> graph;
        unordered_map<TreeNode*, int> outdegree;
    public:
        vector<vector<int>> findLeaves(TreeNode* root) {
            helper(root);
            vector<vector<int>> res;
            while (outdegree.size()) {
                cout << outdegree.size() << endl;
                vector<int> level;
                vector<TreeNode*> rem;
                for (auto i : outdegree)
                    if (i.second == 0) {
                        level.push_back(i.first->val);
                        rem.push_back(i.first);
                    }
                for (auto i : rem) {
                    if (graph.find(i) != graph.end())
                        outdegree[graph[i]]--;
                    outdegree.erase(i);
                }
    
                res.push_back(level);
            }
            return res;
        }
    };
    

Log in to reply
 

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