题解 | #二叉树中和为某一值的路径(二)#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int temp[1500] ={0};
static int g_num = 0;
int get_tree_depth(struct TreeNode* root)
{
    if (root == NULL) {
        return 0;
    }
    int left_depth = get_tree_depth(root->left);
    int right_depth = get_tree_depth(root->right);
    return ((left_depth > right_depth) ? left_depth : right_depth) + 1;
}
void save_tree_node_left_to_right(struct TreeNode* root, int level)
{
    if (root == NULL) {
        return;
    }
    if (level == 0) {
        temp[g_num++] = root->val;
    }
    else {
        save_tree_node_left_to_right(root->left, level -1);
        save_tree_node_left_to_right(root->right, level - 1);
    }
}

void save_tree_node_right_to_left(struct TreeNode* root, int level)
{
    if (root == NULL) {
        return;
    }
    if (level == 0) {
        temp[g_num++] = root->val;
    } else {
        save_tree_node_right_to_left(root->right, level -1);
        save_tree_node_right_to_left(root->left, level - 1);
    }
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if (pRoot == NULL) {
        return NULL;
    }
    int tree_depth = get_tree_depth(pRoot);
    int **array = (int **)malloc(sizeof(int *) * 1500); /* 节点最大1500 */
    (*returnColumnSizes) = (int *)malloc(sizeof(int) * 1500);
    (*returnSize) = 0;

    for (int i = 0; i < tree_depth; i++) {
        g_num = 0;
        if (i & 0x1) {  /* 奇数层 */
            save_tree_node_right_to_left(pRoot, i);
        } else {
            save_tree_node_left_to_right(pRoot, i);
        }
        array[(*returnSize)] = (int *)malloc(sizeof(int) * g_num);
        memcpy(array[(*returnSize)], temp, sizeof(int) * g_num);
        (*returnColumnSizes)[i] = g_num;
        (*returnSize)++;
    }

    return array;
}