Easy to understand C++ iterative approach


  • 0
    
    class Solution {
    public:
        vector<vector<int>> findLeaves(TreeNode* root) {
            
            vector<vector<int>> res;
            if (!root) { return res; }
            
            unordered_map<TreeNode*,bool> removed;
            while(removed.find(root) == removed.end()){
                
                //
                // current set of leaves for this iteration through the tree
                //
                vector<int> leaves;
                
                //
                // dfs
                //
                vector<TreeNode*> stack;
                stack.push_back(root);
                while (!stack.empty()){
                    TreeNode* curr = stack.back();
                    stack.pop_back();
                    
                    //
                    // check for real leaf node, or new leaf node due to prevoius removals
                    //
                    bool left = true;
                    bool right = true;
                    
                    if ( !curr->left || removed.find(curr->left) != removed.end() ){
                        left = false;
                    }
                    if ( !curr->right || removed.find(curr->right) != removed.end() ){
                        right = false;
                    }
                    
                    if ( !left && !right ) {
                        
                        leaves.push_back(curr->val);
                        removed[curr]=true;
                    }
                
                    //
                    // iterate through the rest of the tree
                    // by adding non-NULL and non-removed nodes onto the stack
                    //
                    if (left)  { stack.push_back(curr->left);  }
                    if (right) { stack.push_back(curr->right); }
                }
                
                //
                // add current set of leaves onto the end-result
                //
                res.push_back(leaves);
            }
        
            return res;
        }
    };
    

Log in to reply
 

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