C++, easy to understand, O(n) 3ms


  • 0
    Z

    We can easily build the tree using a vector<vector<int>>:

    tree[dep][pos] = val; 
    

    If pos of the parent node = k,
    left child = 2k
    right child = 2k+1

           0
       0       1
     0   1   2   3
    0 1 2 3 4 5 6 7
    

    Then iterate through the tree level by level, update path sum from root to each node, and add all leaves to the sum.

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            if (nums.empty()) return 0;
            vector<int> tree(8, 0);
            int dep = nums.back()/100, n = nums.size(), ans = 0;
            for (int i = 1, j = 0; i <= dep; i++) {
                vector<int> tmp(8, 0);
                // fill path sum in nodes of each level
                while (j < n && nums[j]/100 == i) {
                    int pos = nums[j]%100/10-1;
                    tmp[pos] = nums[j++]%10 + tree[pos/2];
                }
                // if both children are null, add the parent leaf node
                // also work for node value of 0, such as 210
                for (int k = 0; k < 4; k++) {
                    if (tmp[k*2] == 0 && tmp[k*2+1] == 0)
                        ans += tree[k];
                }
                swap(tree, tmp);
            }
            return accumulate(tree.begin(), tree.end(), ans);
        }
    };
    

Log in to reply
 

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