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

二叉树中和为某一值的路径(一)

http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param sum int整型 
 * @return bool布尔型
 */
#define ElemType LNode*
typedef struct TreeNode LNode;
#define bool int
//栈结点
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;
}

bool hasPathSum(struct TreeNode* root, int sum ) {
    // write code here
    if(root==NULL)return 0;
    SNode* S = NULL;
    LNode* p = root;
    LNode* r = NULL;
    int value = 0;
    
    while (p || !isEmpty(S)) {
        if (p) {
            Push(&S, p);
            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==sum) {
                    return 1;
                }
                Pop(&S, &p);
                value -= p->val;
                r = p;//记录最近访问过的结点
                p = NULL;//结点访问完后,重置p指针
            }
        }
    }
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
缒梦&独舞:这家公司是这样的,去年给我实习offer了,不过也是面着玩儿的,他周六还要去做公益志愿活动
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务