[c++] dfs


  • 0
    D
    class Solution {
    public:
        // 用三位数来表示一个节点
        // 得到一条路径的和
        void dfs(unordered_map<int, int> &mapping, int index, vector<int> &path, vector<vector<int>> &res) {
            if (mapping.find(index * 2) == mapping.end() && mapping.find(index * 2 + 1) == mapping.end()) {
                path.push_back(mapping[index]);
                res.push_back(path);
                path.pop_back();
                return;
            }
            
            if (mapping.find(index * 2) != mapping.end()) {
                path.push_back(mapping[index]);
                dfs(mapping, index * 2, path, res);
                path.pop_back();
            }
            if (mapping.find(index * 2 + 1) != mapping.end()) {
                path.push_back(mapping[index]);
                dfs(mapping, index * 2 + 1, path, res);
                path.pop_back();
            }
            
        }
        int pathSum(vector<int>& nums) {
            if (nums.empty()) {
                return 0;
            }
            
            unordered_map<int, int> mapping;
            for (auto num : nums) {
                int d = num / 100;
                int index = pow(2, d - 1) - 1;
                int p = num % 100 / 10;
                index += p;
                int v = num % 100 % 10;
                mapping[index] = v;
            }
            
            vector<int> path;
            vector<vector<int>> res;
            dfs(mapping, 1, path, res);
            
            int sum = 0;
            for (auto path : res) {
                for (auto v : path) {
                    sum += v;
                }
            }
            
            return sum;
        }
    };
    

Log in to reply
 

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