Python 1D Array Solution, 55 ms


  • 0
    B

    This solution uses a 1 dimensional array to represent the binary tree and index arithmetic to traverse it. From any node at index location i, the left node is at i+i+1 and right node is at i+i+2.

        def pathSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            a = [None for i in xrange(32)]
            for n in nums:
                t = n % 100
                v = n % 10
                p = (t - v) / 10
                d = (n - t) / 100
                a[2**(d-1)-1 + (p-1)] = v
            def dfs(i, s): 
                if a[i] == None:
                    return 0
                s += a[i]
                l = dfs(2*i + 1, s)
                r = dfs(2*i + 2, s)
                if l == 0 and r == 0:
                    return s
                return l + r
            s = dfs(0, 0)
            return s
    

  • 0
    B

    C++ version completes in 6 ms. I used a hash instead of array, same time complexity.

    class Solution {
    public:
        unordered_map<int, int> a;
        int dfs(int i, int s) {
            if (a.find(i) == a.end()) {
                return 0;
            }
            s += a[i];
            int l = dfs(i+i+1, s);
            int r = dfs(i+i+2, s);
            if (!l && !r) {
                return s;
            }
            return l + r;
        }
    
        int pathSum(vector<int>& nums) {
            for (auto n: nums) {
                int t = n % 100;
                int v = n % 10;
                int p = (t - v) / 10;
                int d = (n - t) / 100;
                a[int(pow(2, (d-1)))-1 + (p-1)] = v;
            }
            return dfs(0, 0);
        }
    };
    

Log in to reply
 

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