50105. Seesaw Chandelier Tree

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "construct.h"

// typedef struct Node{
//     int value;
//     struct Node *left, *right;
// } Node;

int* arr;
int n;

Node *make_left(int l, int r){
    Node *head = (Node*) malloc(sizeof(Node));

    Node *now = head;
    for(int i = r; i >= l; i--){
        Node* temp = (Node*) malloc(sizeof(Node));
        temp->value = arr[i];
        now->left = temp;
        now->right = NULL;
        now = now->left;
    }
    now->left = NULL;
    now->right = NULL;
    return head->left;
}

Node *dfs(int l, int r){
    if(r - l < 2) return make_left(l, r);

    uint64_t l_bucket = 0, r_bucket = 0;
    uint64_t l_weight = 0, r_weight = 0;

    uint64_t p = 0;
    for(int i = l; i <= r; i++){
        r_bucket += arr[i];
        r_weight += (p++) * arr[i];
    }

    for(int i = l; i <= r; i++){
        if(l_weight > r_weight) break;
        else if(l_weight == r_weight){
            Node* torque = (Node*) malloc(sizeof(Node));
            torque->value = arr[i];
            torque->left = dfs(l, i - 1);
            torque->right = dfs(i + 1, r);
            return torque;
        }
        else{
            l_bucket += (uint64_t)arr[i], r_bucket -= (uint64_t)arr[i];
            l_weight += l_bucket, r_weight -= r_bucket;
        }
    }

    return make_left(l, r);
}

Node *ConstructTree(int T[], int N){
    arr = T;
    n = N;
    return dfs(0, n - 1);
}