题解 | #在二叉树中找到累加和为指定值的最长路径长度#

#include <bits/stdc++.h>

using namespace std;

struct TreeNode{ TreeNode * left; TreeNode * right; TreeNode * parent; int val; TreeNode(){ left = NULL; right = NULL; parent = NULL; } };

void getRes(TreeNode * root, vector &node2val,
int sum, int temp_sum, int &level ,int &res, unordered_map<int, int> &sNum2level) { if(root == NULL){ return ; } int temp_num = node2val[root->val]; temp_sum += temp_num;

// 重点在这里
if (sNum2level.find(temp_sum) == sNum2level.end())
{
    sNum2level[temp_sum ] = level;
}
// 首先要更新当前的累加和对应深度，如果之前包含则取小的！！）
if( sNum2level.find(temp_sum -sum ) != sNum2level.end() )
{
    res = max(res, level - sNum2level[temp_sum -sum ]);
    // 更新res
}

level++;
getRes(root->left, node2val,  sum, temp_sum , 
      level, res, sNum2level);
getRes(root->right, node2val,  sum, temp_sum , 
      level, res, sNum2level);

level--;
// 还有这里！！！
if(sNum2level.find(temp_sum) != sNum2level.end() &&
   sNum2level[temp_sum] == level)
{
    sNum2level.erase(temp_sum );
    
}
// 只有对于temp_sum 对应当前深度， 才需要回溯减；
// temp_sum -= temp_num;

}

int main(){ int n, root, sum; int a, b, c, d;

scanf("%d %d",&n,&root);
vector<TreeNode *> mapT(n+1, NULL);
vector<int> node2val(n+1, 0);
TreeNode * node;
for(int i=0;i<n;i++)
{
    scanf("%d %d %d %d",&a,&b,&c,&d);
    node2val[a] = d;
    if(mapT[a] == NULL){
        node = new TreeNode();
        node -> val = a;
        mapT[a] = node;
    }else{
        node = mapT[a];
    }
    
    if(b != 0){
        node -> left = new TreeNode();
        node -> left -> val = b;
        mapT[b] = node->left;
    }
    if(c != 0){
        node -> right = new TreeNode();
        node -> right -> val = c;
        mapT[c] = node->right;
    }
}
cin>>sum;
node = mapT[root];
unordered_map<int, int> sNum2level;
sNum2level[0] = 0;
int res = 0;
int level = 1;
int temp_sum = 0;
getRes(node, node2val, sum, temp_sum, level, res, sNum2level);
cout<<res;

return 0;

}