C++ O(n) DFS solution, no hashmap


  • 0
    M
        int res=0;
        int pathSum(vector<int>& nums) {
            vector<vector<int>> tree(4, vector<int>(8, -1));
            for(int i=0;i<nums.size();i++) tree[nums[i]/100-1][nums[i]%100/10-1]=nums[i]%10; 
            DFS({0, 0}, 0, tree);
            return res;
        }
        
        void DFS(vector<int> r, int sum, vector<vector<int>>& tree) {
            if(r[0]>3) {
                res+=sum;
                return;
            }
            int dep=r[0], pos=r[1], val1=tree[dep][pos*2], val2=tree[dep][pos*2+1];
            if(val1>=0) DFS({dep+1, pos*2}, sum+val1, tree);
            if(val2>=0) DFS({dep+1, pos*2+1}, sum+val2, tree);
            if(val2<0&&val1<0) res+=sum;
        }

Log in to reply
 

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