题解 | #二叉树根节点到叶子节点的所有路径和#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
#define bool int
#define false 0
#define true 1
typedef struct TreeNode LNode;
#define ElemType LNode*

//链栈结点
typedef struct SNode {
    ElemType data;
    struct SNode* next;
}SNode;
typedef struct RNode {
    int data;
    struct RNode* next;
}RNode;
//参数S即为栈顶指针
bool Push(SNode** S, ElemType e) {
    SNode* x = (SNode*)malloc(sizeof(SNode));
    if (x == NULL)return false;
    x->next = *S;
    x->data = e;
    *S = x;
    return true;
}
bool PushR(RNode** R, int e) {
    RNode* x = (RNode*)malloc(sizeof(RNode));
    if (x == NULL)return false;
    x->next = *R;
    x->data = e;
    *R = x;
    return true;
}

bool Pop(SNode** S, ElemType* e) {
    if (*S == NULL)return false;
    *e = (*S)->data;
    SNode* p = *S;
    *S = (*S)->next;
    free(p);p = NULL;
    return true;
}
bool PopR(RNode** R, int* e) {
    if (*R == NULL)return false;
    *e = (*R)->data;
    RNode* p = *R;
    *R = (*R)->next;
    free(p); p = NULL;
    return true;
}
bool isEmpty(SNode* S) {
    if (S == NULL)return true;
    else return false;
}


int sumNumbers(struct TreeNode* root ) {
    // write code here
    if(root==NULL)return 0;
    SNode* S=NULL;//栈顶指针
    RNode* R = NULL;
    Push(&S, root);
    PushR(&R, root->val);
    LNode* L; RNode* T;
    int e;
    int gSum = 0;
    while (!isEmpty(S)) {
        Pop(&S, &L);//弹出栈顶元素
        PopR(&R, &e);
        int value = e;
        if (L->left == NULL && L->right == NULL) {
            gSum += value;
        }
        else {
            if (L->right != NULL) {
                PushR(&R, value * 10 + L->right->val);
                Push(&S, L->right);
            }
            if (L->left != NULL) {
                PushR(&R,value * 10 + L->left->val);
                Push(&S, L->left);
            }
        }
        //cout << L->data << " ";//遍历根结点
        //if (L->right)Push(&S, L->right);//先将右子树入栈
        //if (L->left)Push(&S, L->left);//再将左子树入栈
    }
    return gSum;
}