LeetCode Hot100 | Day7 | 路径总和III

看路径总和III之前先看
112. 路径总和 - 力扣(LeetCode)

class Solution {
public:
    bool flag=false;
    void tra(TreeNode *t,int target)
    {
        if(t==nullptr)
            return ;
        target-=t->val;
        if(t->left==nullptr&&t->right==nullptr)
        {
            if(target==0)
                flag=true;
        }
        tra(t->left,target);
        tra(t->right,target);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        tra(root,targetSum);
        return flag;
    }
};

flag表示最后的结果,是不是找到了路径

本层逻辑

目标值减去本层的数,之后是结果收集的判断,是否是叶子结点,是否已经是目标值,全为是就是true

 		target-=t->val;
        if(t->left==nullptr&&t->right==nullptr)
        {
            if(target==0)
                flag=true;
        }
		tra(t->left,target);
        tra(t->right,target);

之后继续遍历左子树和右子树

437.路径总和III

437. 路径总和 III - 力扣(LeetCode)

本题就不是从根节点到叶子节点,而是任意节点到任意节点,只要满足自顶向下即可

而我们之前用的模板其实是从根节点到叶子结点,接下来这么做

1.把判断是不是叶子节点的if去掉,那就是根节点到任意节点的路径

2.那么怎么从任意节点开始呢?

我们的backtracking是之前的从根节点到叶子节点的路径查询去掉了叶子结点的判断if,那就是根节点到任意路径。而在这道题里面就是当传入的targetSum为0的时候,backtracking就会从传入的节点开始向下搜索。那我们只需重新写一个遍历函数,把每个节点都当成根节点(即参数targetSum为0)传一遍,那每个节点都会向下搜索路径,所以tra就是遍历这课树,遍历的时候让backtracking从当前结点开始向下搜索找到合适的路径,然后记录结果

class Solution {
public:
    long long sum=0;
    void tra(TreeNode *t,long long targetSum)
    {
        if(t==nullptr)
            return;
        backtracking(t,targetSum);
        tra(t->left,targetSum);
        tra(t->right,targetSum);
    }
    void backtracking(TreeNode *t,long long targetSum)
    {
        if(t==nullptr)
            return;
        targetSum-=t->val;
        if(targetSum==0)
            sum++;
        backtracking(t->left,targetSum);
        backtracking(t->right,targetSum);
    }
    int pathSum(TreeNode* root, int targetSum) {
        tra(root,targetSum);
        return sum;
    }
};

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部