题目描述

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

保证树中结点值均不小于 0。

数据范围
树中结点的数量 [0,1000]。

样例

给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]

算法1

(dfs) $O(n)$

解析看y总

C 代码

int len[1000];
int row=0,col=0;
void dfs(int** ret,struct TreeNode *now,int sum){
    int i;
    if(now->val > sum) return;                  //题目说了全是正数 因此可以剪枝 当本节点值已经大于目标值时
    else if(now->left == NULL && now->right==NULL && now->val == sum){  //叶结点且正好符号
        ret[row][col++]=now->val;
        len[row++]=col;                         //记录本行节点数
        for(i=0;i<col;i++) ret[row][i]=ret[row-1][i];   //将本行数据 复制到下一行
        col--;                                  //回退
        return;
    }
    else{
        ret[row][col++]=now->val;               //记录
        if(now->left!=NULL) dfs(ret,now->left,sum-now->val);    //左右递归
        if(now->right!=NULL) dfs(ret,now->right,sum-now->val);
    }
    col--;                                      //回退
}
int** findPath(struct TreeNode* root, int sum, int** columnSizes, int* returnSize) {
    int i;
    int **ret=(int**)malloc(sizeof(int*)*1000);                     //申请矩阵
    for(i=0;i<1000;i++) ret[i]=(int*)malloc(sizeof(int)*1000);
    **columnSizes=0;                                                //初始化为空
    *returnSize=0;
    if(root==NULL) return ret;                                      //空就返回

    dfs(ret,root,sum);                      //递归深搜

    *returnSize=row;                                                //更新行列数
    for(i=0;i<row;i++) *(*columnSizes+i)=len[i];

    return ret;
}