LeetCode437 路径总和III

发表于 | 分类于 |
字数统计: 224 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/path-sum-iii/

题意

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

解法

使用dfs进行搜索，计算节点值的和是否可以等于targetSum
但由于不一定从根节点出发，所以需要分情况考虑

  1. 选取该节点加入路径，之后必须连续加入或停止加入
  2. 不选取当前节点，则对其左右节点进行考虑
    所以使用两个递归函数完成计数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(TreeNode* root, int target) {
        if (root == nullptr) return 0;
        int count = (root -> val == target);
        count += dfs(root -> left, target - root -> val);
        count += dfs(root -> right, target - root -> val);
        return count;

    }
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return 0;
        int ans = dfs(root, targetSum) + pathSum(root -> left, targetSum) + pathSum(root -> right, targetSum);
        return ans;
    }
};