C++ recursion with a hash table: clumsy but easy to understand, 20ms


  • 0
    S

    First idea:
    Here we need to record the parent node and the original value.
    Ideally, in some language supporting dynamic properties, we can attach the parent and old value to each node. However, this is not supported in c++.
    A workaround is to use a hash table to map each node --> parent and old value.

    class Solution {
        std::unordered_map<TreeNode*, std::pair<TreeNode*, int>> map; // for each node p, record the parent node and p's value
        std::vector<TreeNode*> qualifiedLeaves;
        // find the leaf nodes whose path sum is the given one
        void findQualifiedLeaves(TreeNode* root, int sum){
            if (root == nullptr)
                return;
            if (root->left == nullptr && root->right == nullptr){ // a leaf node
                if (root->val == sum)
                    qualifiedLeaves.push_back(root);
            }
            if (root->left != nullptr){
                map.emplace(root->left, std::make_pair(root, root->left->val)); 
                root->left->val += root->val;
                findQualifiedLeaves(root->left, sum);
            }
            if (root->right != nullptr){
                map.emplace(root->right, std::make_pair(root, root->right->val)); 
                root->right->val += root->val;
                findQualifiedLeaves(root->right, sum);
            }
        }
        
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            std::vector<std::vector<int>> paths;
            if (root == nullptr)
                return paths;
            map.emplace(root, std::make_pair(nullptr, root->val));
            findQualifiedLeaves(root, sum);
            
            for (auto p: qualifiedLeaves){// for each qualified leaf, we track back to the root
                std::vector<int> path;
                TreeNode* parent = nullptr;
                int val = 0;
                while (p != nullptr){ // backtracking
                    std::tie(parent, val) = map[p];
                    path.push_back(val);
                    p = parent;
                }
                std::reverse(path.begin(), path.end());
                paths.emplace_back(std::move(path));
            }
            return paths;
            
        }
    };
    

Log in to reply
 

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