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

/**
 * 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 ElemType LNode*
typedef struct TreeNode LNode;

//栈结点
typedef struct SNode {
    struct SNode* next;
    ElemType e;
}SNode;

int isEmpty(SNode* S) {
    if (S == NULL)return 1;
    else return 0;
}

int Push(SNode** S, ElemType f) {
    SNode* x = (SNode*)malloc(sizeof(SNode));
    if (x == NULL)return 0;
    x->e = f;
    x->next = *S;
    *S = x;
    return 1;
}
int Pop(SNode** S, ElemType* e) {
    *e = (*S)->e;
    SNode* p = *S;
    *S = (*S)->next;
    free(p); p = NULL;
    return 1;
}

int** FindPath(struct TreeNode* root, int target, int* returnSize, int** returnColumnSizes ) {
    // write code here
    //*returnSize=0;
    //**returnColumnSizes=0;
    if(root==NULL)return NULL;
    SNode* S = NULL;
    LNode* p = root;
    LNode* r = NULL;
    int value = 0;
    int count = 0;
    (*returnColumnSizes) = (int *)malloc(sizeof(int) * (5));
    int** z = (int**)malloc(sizeof(int*) * 5);
    *returnSize=0;
    //if (z == NULL)return NULL;
    while (p || !isEmpty(S)) {
        if (p) {
            Push(&S, p);
            count++;
            value += p->val;
            p = p->left;
        }
        else {
            p = S->e;
            if (p->right && p->right != r) {//若右子树存在，且未被访问过
                p = p->right;
            }
            else {
                if (S->e->left == NULL && S->e->right == NULL&&value==target) {
                    int* tmp= (int*)malloc(sizeof(int) * count);
                    (*returnColumnSizes)[*returnSize]=count;
                    //if (tmp == NULL)return NULL;
                    int i = count - 1;
                    SNode* T = S;
                    while (T) {
                        tmp[i] = T->e->val;
                        T = T->next;
                        i--;
                    }
                    z[(*returnSize)] = tmp;
                    (*returnSize)++;
                }
                Pop(&S, &p);
                value -= p->val;
                count--;
                r = p;//记录最近访问过的结点
                p = NULL;//结点访问完后，重置p指针
            }
        }
    }
    return z;
}