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

//通用回溯方法的实现,用一个临时的数组来进行回溯
//当符合条件时申请空间保存回溯结果
#define MaxSize 5000
int tempPath[MaxSize];
int row = 0;
int col[MaxSize];
int tempDepth = 0;
int **path;

//int road[depth];
int TreeDepth(struct TreeNode *root)
{
  if (!root)
    return 0;
  int LD, RD;
  LD = TreeDepth(root->left);
  RD = TreeDepth(root->right);
  return (LD > RD ? LD : RD) + 1;
}

void preOrder(struct TreeNode *root, int target)
{

  if (!root)
    return;
  tempPath[tempDepth++] = root->val;
//回溯结束条件
  if (!root->left && !root->right && root->val == target)
  {
    // path[row] = tempPath; 这里不能给path这样赋值,否则相当于把path这一行的指针指向tempPath
    //会导致结果随着tempPath更新而更新,这里可以通过循环遍历赋值
    //也可以通过memcpy函数进行粘贴,同时可以在此处再为path分配空间
    path[row] = (int *)malloc(sizeof(int) * tempDepth);
    memcpy(path[row], tempPath, sizeof(int) * tempDepth);
    col[row] = tempDepth;
    row++;
  }

  preOrder(root->left, target - root->val);
  preOrder(root->right, target - root->val);
  //回溯,撤销操作
  tempDepth--;
  
}

int **FindPath(struct TreeNode *root, int target, int *returnSize, int **returnColumnSizes)
{
  if (!root)
    return NULL;

  //计算树的深度
  int depth = TreeDepth(root);
  path = (int **)malloc(sizeof(int *) * pow(2, depth));
  // for (int i = 0; i < 5000; i++)
  //   path[i] = (int *)malloc(sizeof(int) * depth);
  *returnSize = 0;
  (*returnColumnSizes) = (int *)malloc(sizeof(int) * depth);

  preOrder(root, target);
  *returnSize = row;
  *returnColumnSizes = col;
  return path;
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param target int整型 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
#define MaxSize 5000

//int road[depth];
int TreeDepth(struct TreeNode *root)
{
  if (!root)
    return 0;
  int LD, RD;
  LD = TreeDepth(root->left);
  RD = TreeDepth(root->right);
  return (LD > RD ? LD : RD) + 1;
}

void preOrder(struct TreeNode *root, int target, int **path, int *returnSize, int **returnColumnSizes)
{

  path[*returnSize][(*returnColumnSizes)[*returnSize]++] = root->val;
  target -= root->val;

  if (!root->left && !root->right && target == 0)
  {
    for (int i = 0; i < (*returnColumnSizes)[*returnSize]; i++)
    {
      path[(*returnSize) + 1][i] = path[*returnSize][i];
    }
    (*returnColumnSizes)[(*returnSize) + 1] = (*returnColumnSizes)[*returnSize];
    (*returnSize)++;
    return;
  }
  else if (!root->left && !root->right && target != 0)
  {
    return;
  }
  if (root->left)
  {
    preOrder(root->left, target, path, returnSize, returnColumnSizes);
    (*returnColumnSizes)[*returnSize]--;
  }
  if (root->right)
  {
    preOrder(root->right, target, path, returnSize, returnColumnSizes);
    (*returnColumnSizes)[*returnSize]--;
  }
  
}

int **FindPath(struct TreeNode *root, int target, int *returnSize, int **returnColumnSizes)
{
  if (!root)
    return NULL;
  int **path;
  //计算树的深度
  int depth = TreeDepth(root);
  path = (int **)malloc(sizeof(int *) * MaxSize);
  for (int i = 0; i < 5000; i++)
    path[i] = (int *)malloc(sizeof(int) * depth);
  *returnSize = 0;
  (*returnColumnSizes) = (int *)malloc(sizeof(int) * depth);
  (*returnColumnSizes)[*returnSize] = 0;

  preOrder(root, target, path, returnSize, returnColumnSizes);
  return path;
}