C++ flatten the tree clean solution


  • 0
    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            int n = nums.size();
            vector<int> temp(16, -1); //As the max depth of tree is 5 the total nodes will be 2^(depth)-1;
            
            for (int i=0;i<n;i++){
                string arr = to_string(nums[i]);
                int depth = arr[0]-'0';
                int level = arr[1]-'0';
                int value = arr[2]-'0';
                int idx = (1<<(depth-1)) + level - 1; //calculate the index of the node in temp array
                temp[idx] = value;
            }
            
            int res=0;
            for (int i=temp.size()-1;i>0;i--){
                //If the node is a leaf i.e. (i>7 || temp[2*i]==-1 && temp[2*i+1]==-1) then sum the path from leaf till the root
                if (temp[i] != -1 && (i>7 || (temp[2*i]==-1 && temp[2*i+1]==-1))){
                    int j=i;
                    while (j>0){
                        res += temp[j];
                        j = j/2;
                    }   
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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