剑指Offer | 二叉树中和为某一值的路径(三)

秦怀杂货店

发布于 2022-02-15 15:05:50

2330

发布于 2022-02-15 15:05:50

文章被收录于专栏：技术杂货店

Part0前言

剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 刷题仓库介绍：刷题仓库：CodeSolution 编程知识库：https://github.com/Damaer/Coding 文档地址：https://damaer.github.io/Coding/#/ 剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~ 了解数据结构可以点击：万字长文带你漫游数据结构世界

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

1题目描述

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为 n
3.保证最后返回的路径个数在整形范围内

假如二叉树 root为 {1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，

2思路 & 解答

这道题值得注意的是，开始不一定在根节点，结束也不一定在叶子节点，因此每个节点都可以往下递归查找的。

每次查找到一个节点的时候，用 sum 减去当前节点的值，如果等于 0，就说明前面的节点到当前节点满足和为 sum，此时注意不要 return，因为下面还需要继续查找，比如存在-1 和 1 的路径，加起来还是会满足的。

如果不想在递归中来回传递变量，可以使用一个全局变量来保存结果：

public class Solution84 {
    public int sum = 0;

    public void dfs(TreeNode root, int sum) {
        if (null == root) return;
        sum -= root.val;
        if (sum == 0) {
            this.sum++;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }

    public int FindPath(TreeNode root, int sum) {
        if (null == root) return this.sum;
        // 当前节点往下遍历
        dfs(root, sum);
        // 在左子树查找（不包括当前节点）
        FindPath(root.left, sum);
        // 在右子树查找（不包括当前节点）
        FindPath(root.right, sum);
        return this.sum;
    }
}

C++ 代码如下：

class Solution {
public:
    int sum = 0;

    int FindPath(TreeNode *root, int sum) {
        if (NULL == root) return this->sum;
        // 当前节点往下遍历
        dfs(root, sum);
        // 在左子树查找（不包括当前节点）
        FindPath(root->left, sum);
        // 在右子树查找（不包括当前节点）
        FindPath(root->right, sum);
        return this->sum;
    }

    void dfs(TreeNode *root, int sum) {
        if (NULL == root) return;
        sum -= root->val;
        if (sum == 0) {
            this->sum++;
        }
        dfs(root->left, sum);
        dfs(root->right, sum);
    }
};

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人网站：http://aphysia.cn ,关注我，我们一起成长吧~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-01-15，如有侵权请联系 cloudcommunity@tencent.com 删除

https