#include <stdio.h>
#include <stdlib.h>

#define max(a,b) a>b ? a:b

typedef struct treenode {
    int val;
    struct treenode *right;
    struct treenode *left;
}TreeNode;

typedef struct listnode {
    int val;
    struct listnode *next;
}ListNode;


ListNode * heaviest(TreeNode *root, ListNode **heavy) {
    if (root==NULL)
        return NULL;
    else (*heavy)->val=root->val;
    if (root->left==NULL && root->right==NULL) {
        (*heavy)->next=NULL;
        return *heavy;
    }
    else (*heavy)->next=(ListNode *)malloc(sizeof(ListNode));
    if (root->left==NULL){
        (*heavy)->next=heaviest(root->right, &((*heavy)->next));
        return *heavy;
    }
    else if (root->right==NULL){
        (*heavy)->next=heaviest(root->left, &((*heavy)->next));
        return *heavy;
    }
    else {
        if (maxSum(root->left) > maxSum(root->right))
            (*heavy)->next=(heaviest(root->left,&((*heavy)->next)));
        else (*heavy)->next=(heaviest(root->right,&((*heavy)->next)));
        return *heavy;
    }

}

int maxSum(TreeNode *root) {
    if (root==NULL)
        return 0;
    else if (root->left==NULL && root->right==NULL)
        return root->val;
    else if (root->left==NULL)
        return root->val + maxSum(root->right);
    else if (root->right==NULL)
        return root->val + maxSum(root->left);
    else return  root->val + max(maxSum(root->left), maxSum(root->right));
}