algo-aha

最大路径和，路径不必经过根节点

• https://leetcode.com/problems/binary-tree-maximum-path-sum/

int maxPathSum(TreeNode* root) {
    int ans = INT_MIN;
    arrowSum(root, ans);
    return ans;
}

// 返回从root往下的最大路径和
int arrowSum(TreeNode *root, int &ans) {
    if (!root) return 0;
    int left = arrowSum(root->left, ans);
    int right = arrowSum(root->right, ans);
    int arrow = root->val + max({0, left, right});

    // 经过root的最大路径和
    int pathSum = root->val + max(0, left) + max(0, right);
    ans = max(ans, pathSum);

    return arrow;
}

向下路径和为target的路径有多少条

• https://leetcode.com/problems/path-sum-iii/

平均O(nlgn)，最坏O(n^2)

int pathSum(TreeNode* root, int sum) {
    if (!root) return 0;
    return searchFrom(root, sum)
        + pathSum(root->left, sum) 
        + pathSum(root->right, sum);
}

int searchFrom(TreeNode *root, int sum) {
    if (!root) return 0;
    return (root->val == sum ? 1 : 0) 
        + searchFrom(root->left, sum - root->val)
        + searchFrom(root->right, sum - root->val);
}

子段和的runningSum解法，O(n)

int pathSum(TreeNode *root, int target) {
    unordered_map<int, int> presum = {{0,1}}; // sum=>count
    int runningSum = 0;
    int ans = 0;
    search(root, target, runningSum, presum, ans);
    return ans;
}

void search(TreeNode *root, int target, int runningSum, 
            unordered_map<int, int> &presum, int &ans) {
    if (!root) return;

    // 以当前节点结尾的子数组，希望能找到数组子段和runningSum-toFind=target
    runningSum += root->val;
    int toFind = runningSum - target;
    if (presum.count(toFind)) ans += presum[toFind];

    presum[runningSum]++;
    search(root->left, target, runningSum, presum, ans);
    search(root->right, target, runningSum, presum, ans);
    presum[runningSum]--; // 回溯，为其他搜索路径准备
}