Using heap-like array to construct the tree with detail explaination


  • 0
    A

    As the tree is described as a level and position style given the list of integers, it is quite nature to consider using an array to represent the tree. The idea is the same as when we study the heap data structure using an array to implement.

    Using an array rather than pointer to represent the tree has its advantage and disadvantage. The good thing is that all the data are in the contiguous region in the memory. The memory access is pretty good. The draw back is that you may waste a lot of memory, especially if you have a very deep and skewed tree. That's why pointer is mostly used for its dynamically allocation. Coming back to this question, as the depth is bounded, an array representation is pretty good choice.

    class Solution {
    public:
        bool isLeaf(vector<int>& tree, int node) {
            if (2 * node + 1 >= tree.size()) {
                return true;
            }
            return (tree[2 * node + 1] == -1 && tree[2 * node + 2] == -1);
        }
        
        void computePathSum(vector<int>& tree, int node, int& sum, int& tot_sum) {
            if (node >= tree.size()) {
                return;
            }
            if (tree[node] == -1) {
                return;
            }    
            sum += tree[node];
            if (isLeaf(tree, node)) {
                tot_sum += sum; 
            } 
            computePathSum(tree, 2 * node + 1, sum, tot_sum);
            computePathSum(tree, 2 * node + 2, sum, tot_sum);
            sum -= tree[node];
        }
        
        int pathSum(vector<int>& nums) {
            vector<int> tree(15, -1);
            for (int i=0; i<nums.size(); i++) {
                int level = nums[i] / 100;
                int pos = (nums[i] % 100) / 10;
                int val = nums[i] % 10;
                int heap_pos = (1 << (level - 1)) - 1 + (pos - 1);
                tree[heap_pos] = val;
            }
            int sum = 0;
            int tot_sum = 0;
            computePathSum(tree, 0, sum, tot_sum);
            return tot_sum;
        }
    };
    

Log in to reply
 

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