leetcode437：路径总和III

题目链接

leetcode

题目描述

给定一个二叉树的根节点 root 和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    深度优先搜索：
        穷举所有可能，访问每一个结点，检测以该结点为起始结点且向下的路径有多少种。
        递归遍历每一个结点所有可能的路径，然后将这些路径数目相加作为结果。
    递归函数定义：
        返回以结点 p 为起点向下且满足路径总和为 val 的路径数目。

    时间复杂度：O(n^2)
        其中 n 为该二叉树结点的个数。
        对于每一个结点，需要遍历以该结点为根结点的子树的所有结点，
        对每个结点都求一次以该结点为起点的路径数目，因此时间复杂度为 O(n^2)。
    空间复杂度：O(n)
*/
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return 0;
        }

        int res = dfs(root, targetSum);
        res += pathSum(root->left, targetSum);
        res += pathSum(root->right, targetSum);

        return res;
    }

    int dfs(TreeNode* node, long long targetSum) {
        if (node == nullptr) {
            return 0;
        }

        long long res = 0;
        if (node->val == targetSum) {
            res++;
        }
        res += dfs(node->left, targetSum - node->val);
        res += dfs(node->right, targetSum - node->val);

        return res;
    }
};

/*
    前缀和

    结点前缀和的定义：由根结点到当前结点的路径上所有结点的和。
    先序遍历二叉树，记录根结点 root 到当前结点 p 的路径上除当前结点以外所有结点的前缀和，
    在已保存的路径前缀和中查找，是否存在等于当前结点到根结点的前缀和 cur-targetSum。
    
    时间复杂度：O(n)
        其中 n 为二叉树中结点的个数。利用前缀和只需遍历一次二叉树。
    空间复杂度：O(n)
*/
class Solution_1 {
public:
    int pathSum(TreeNode* root, int targetSum) {
        sum2cnt[0] = 1; // 初始化
        return dfs(root, targetSum, 0);
    }

    int dfs(TreeNode* root, int targetSum, long long curSum) {
        if (root == nullptr) {
            return 0;
        }

        int res = 0;
        curSum += root->val;
        if (sum2cnt.count(curSum-targetSum)) {
            res = sum2cnt[curSum-targetSum];
        }
        // 选择，更新前缀和计数器
        sum2cnt[curSum]++;
        res += dfs(root->left, targetSum, curSum);
        res += dfs(root->right, targetSum, curSum);
        // 回溯，恢复前缀和计数器
        sum2cnt[curSum]--;

        return res;
    }

private:
    unordered_map<long long, int> sum2cnt;
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {10,5,-3,3,2,NULL_NODE,11,3,-2,NULL_NODE,1},
        {5,4,8,11,NULL_NODE,13,4,7,2,NULL_NODE,NULL_NODE,5,1}
    };
    vector<int> sum_cases = {
        8, 22
    };

    for (int i = 0; i < root_cases.size(); i++) {
        auto& nums = root_cases[i];
        int targetSum = sum_cases[i];
        cout << "Input: ";
        printArray(nums);
        cout << ", targetSum = " << targetSum << endl;

        // 创建二叉树
        TreeNode* root = createTree(nums);
        // 找出所有路径总和等于目标和的所有路径的数量
        int res = solution.pathSum(root, targetSum);
        cout << "Output: " << res << endl;

        // 释放内存
        deleteTree(root);
    }

    return 0;
}