程序员代码面试指南 3.6：二叉树中找累加和为指定值的路径

1、思路

• 前序遍历的同时计算从根节点到当前节点路径之和，哈希表的键表示路径前缀和，值表示路径终点所在的层（因为路径只能由上自下）；

• 遍历过程中若在哈希表中找到curSum - targetSum，则表示已经找到一条累加和为指定值的路径，更新其路径长度；

• 哈希表初始化hash[0] = 0，表示第0层的路径和为0。

2、代码

#include <iostream>
#include <unordered_map>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root, int &n)     //建树
{
    if (n == 0) return;

    int fa, left, right, val;
    cin >> fa >> left >> right >> val;

    root->val = val;
    if (left != 0)
    {
        root->left = new TreeNode(left);
        createTree(root->left, -- n);
    }

    if (right != 0)
    {
        root->right = new TreeNode(right);
        createTree(root->right, -- n);
    }
}

int preOrder(TreeNode *root, int targetSum, int preSum, int level, int maxLen, 
             unordered_map<int, int> &hash)
{
    if (root == nullptr) return maxLen;

    int curSum = preSum + root->val;

    //若上层已有相同的curSum，则不更新，因为用上层的会使路径更长
    if (hash.find(curSum) == hash.end()) 
    {
        hash[curSum] = level;            //将当前层的curSum加入到哈希表中
    }

    if (hash.find(curSum - targetSum) != hash.end())
    {
        maxLen = max(maxLen, level - hash[curSum - targetSum]);
    }

    //继续遍历左右子树
    maxLen = max(preOrder(root->left, targetSum, curSum, level + 1, maxLen, hash), 
                 preOrder(root->right, targetSum, curSum, level + 1, maxLen, hash));

    if (hash[curSum] == level)          //回溯到上一层时，把当前层的curSum移除
    {
        hash.erase(curSum);
    }

    return maxLen;
}

int main()
{
    int n, fa;
    cin >> n >> fa;

    TreeNode *root = new TreeNode(0);
    createTree(root, n);

    int targetSum;
    cin >> targetSum;

    unordered_map<int, int> hash;
    hash[0] = 0;

    cout << preOrder(root, targetSum, 0, 1, 0, hash) << endl;

    return 0;
}