二叉树中累加和为指定值的最长路径

发表于 | 分类于 |

问题

给定一棵二叉树的头节点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_map::value_type(0, 0)); level值初始为0，保证只有一个节点的树的情况，上述算法也能正常运行。

C++小技巧

  • end返回指向当前list对象中末尾之后的元素的迭代器
  • 遍历收集信息过程与返回最长路径两函数分离，使得代码结构清晰易懂。
  • 以传参的方式，更新map以及maxlen变量。减少全局变量，提高代码的安全性