112-路径总和

LeetCode 112. Path Sum

LeetCode-112

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

method: 回溯

这里不需要遍历整棵树，只要找到一个解就可以返回，所以需要返回值

这里是先判断左右节点非空才递归，也可以不管空不空先递归，再判断节点是否为空
用减法可以少个参数

bool traversal(TreeNode* cur, int count) {
    if (!cur->left && !cur->right) {
        if (count == cur->val) return true;
    }
    if (cur->left) {
        if (traversal(cur->left, count - cur->val)) 
            return true;
    }
    if (cur->right) {
        if (traversal(cur->right, count - cur->val)) 
            return true;
    }
    return false;
}

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    return traversal(root, targetSum);
}

可以先直接递归，遇到空节点再判空，不过这样就要遍历整棵树

bool dfs(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) {
        if (targetSum == root->val) return true;
    }
    bool leftSum = dfs(root->left, targetSum - root->val);
    bool rightSum = dfs(root->right, targetSum - root->val);
    return (leftSum || rightSum);   // 找到一个解就行
}
bool hasPathSum(TreeNode* root, int targetSum) {
    return dfs(root, targetSum);
}

---

LeetCode 113. Path Sum II

LeetCode-113

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

method: 回溯

可以把path插值和target减法提到开头位置

vector<vector<int>> res;
vector<int> path;
void dfs(TreeNode *root, int target) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right && target == root->val) {
        res.push_back(path);
    }
    dfs(root->left, target - root->val);
    dfs(root->right, target - root->val);
    path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    if (!root) return res;
    dfs(root, targetSum);
    return res;
}

---

LeetCode 437. Path Sum III

LeetCode-437

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

method 1：嵌套递归

对于每个节点都要考虑取或不取该节点的情况，不取该节点由pathSum递归，取该节点由dfs递归

int dfs(TreeNode *root, long target) {
    if (!root) return 0;
    int res = 0;
    if (root->val == target) res += 1;
    res += dfs(root->left, target - root->val); // 用了root的值
    res += dfs(root->right, target - root->val);
    return res;
}
int pathSum(TreeNode* root, int targetSum) {
    if (!root) return 0;
    int res = dfs(root, targetSum);
    res += pathSum(root->left, targetSum);  // 没有用root的值
    res += pathSum(root->right, targetSum);
    return res;
}

method 2：前缀和

cur记录从根节点到当前节点的前缀和，并且保存在哈希表中，如果当前节点的前缀和减去target值在哈希表中，说明在从根节点到当前节点的路径上存在某点node，使得node到当前节点的前缀和为target

hash<prefix(root-->currentNode), frequency>

hash[0]=1记录cur-target=0的哈希值，说明从根节点到当前节点的前缀和刚好等于target

unordered_map<long, int> hash;
int dfs(TreeNode *root, long cur, int target) {
    if (!root) return 0;
    int res = 0;
    cur += root->val;
    res += hash[cur - target];  // 有等于target的前缀和值就累加
    hash[cur]++;    // 记录当前节点的前缀和，向下层递归
    res += dfs(root->left, cur, target);
    res += dfs(root->right, cur, target);
    hash[cur]--;    // 回溯取消当前节点的前缀和
    return res;
}
int pathSum(TreeNode* root, int targetSum) {
    hash[0] = 1;
    return dfs(root, 0, targetSum);
}