问题
给定一棵二叉树的头节点head和一个32位整数sum,二叉树节点值类型为整型,求累加和为sum的最长路径长度.
路径是指从某个节点往下,每次最多选择一个孩子节点或者不选所形成的节点链
思路
本题的算法原型为:在数组中找到累加和为指定值的最长子数组
。我们只需将每条路径当做数组问题求解
即可。此路径为从根节点出发到叶子节点的节点链。
在求累加和为指定值的最长子数组问题中,我们需要一个键值为sum(0到i位置的累加和),元素值为index(i位置的下标)的哈希表
。用此哈希表来记录sum最早出现的位置
,故若在后面位置出现哈希表中已有的sum值,其index不需要更新
。
求以i位置结尾的累加和为指定值的子数组的长度len
,用i将数组中的每个位置遍历一遍,不断更新,最终便可得到符合要求的最长子数组。
假设指定累加和为k,i位置的sum为S,我们可以得到如下等式关系:(S - k) + k = S.
由此等式我们可知,只要找到sum值为S - k的位置,其下一个位置 到i所有元素组成的子数组,即为以i位置结尾的累加和为指定值的子数组
。而sum值为S - k的位置,我们只需查表即可得到。
前序遍历收集信息,找到二叉树中累加和为指定值的过程放在递归的前面
。一条路径遍历完成,向上回退到合适位置,即在结点的右孩子方向开始下一路径
需要一个level变量实现回退机制
,记录当前节点所在层数。在回退的过程中,remove掉哈希表中的节点
核心代码
int preOrder(treeNode *head, int maxlen, int k, int preSum
, int level, unordered_map<int, int>sumMap)
{
if (head == NULL)
{
return maxlen;
}
int curSum = preSum + head->data;
unordered_map<int, int>::iterator it;
it = sumMap.end();
//map中无curSum值,则插入
if (sumMap.find(curSum) == it)
{
sumMap.insert(unordered_map<int, int>::value_type(curSum, level));
}
if (sumMap.find(curSum - k) != it)
{
maxlen = max(maxlen, level - sumMap.find(curSum - k)->second);
}
maxlen = preOrder(head->l, maxlen, k, curSum, level + 1, sumMap);
maxlen = preOrder(head->r, maxlen, k, curSum, level + 1, sumMap);
// 回退机制,第一次出现cursum的层数等于当前层数,故说明此cursum由当前节点带来的。
// 回退时需要删除map中的记录
if (level == sumMap.find(curSum)->second)
{
sumMap.erase(sumMap.find(curSum));
}
return maxlen;
}
int getMaxLength(treeNode *head, int k)
{
unordered_map<int, int>sumMap;
// 初始化,很重要。根结点的level值为1
sumMap.insert(unordered_map<int, int>::value_type(0, 0));
return preOrder(head, 0, k, 0, 1, sumMap);
}
sumMap初始化
sumMap.insert(unordered_maplevel值初始为0,保证只有一个节点的树的情况,上述算法也能正常运行。
C++小技巧
end
返回指向当前list对象中末尾之后的元素的迭代器
遍历收集信息过程与返回最长路径两函数分离
,使得代码结构清晰易懂。- 以
传参
的方式,更新map以及maxlen变量。减少全局变量,提高代码的安全性