左神算法：在二叉树中找到累加和为指定值的最长路径长度（Java版）

本题来自左神《程序员代码面试指南》“在二叉树中找到累加和为指定值的最长路径长度”题目。

题目

给定一棵二叉树的头节点 head 和一个 32 位整数 sum，二叉树节点值类型为整型，求累加和为 sum 的最长路径长度。“路径” 是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。

例如，二叉树如图 3-16 所示。

如果 sum=6，那么累加和为 6 的最长路径为：-3，3，0，6，所以返回 4。
如果 sum=-9，那么累加和为 -9 的最长路径为：-9，所以返回 1。

注：本题不用考虑节点值相加可能溢出的情况。

题解

相似问题：“求未排序数组中累加和为规定值的最长子数组长度” 问题

如果二叉树的节点数为N，本文的解法可以做到时间复杂度为O(N)，额外空间复杂度为O(h)，其中 h 为二叉树的高度。

具体过程如下：

1．二叉树头节点 head 和规定值 sum 已知；生成变量 maxLen，负责记录累加和等于 sum 的最长路径长度。
2．生成哈希表sumMap。负责记录从 head 开始的一条路径上的累加和出现的情况，累加和也是从 head 节点的值开始累加的。

• key 值代表某个累加和
• value 值代表这个累加和在路径中最早出现的层数。

如果在遍历到 cur 节点时，我们能够知道从 head 到 cur 节点这条路径上的累加和出现的情况，那么求以 cur 节点结尾的累加和为指定值的最长路径长度就非常容易。究竟如何去更新sumMap，才能够做到在遍历到任何一个节点时，都能有从 head 到这个节点的路径上的累加和出现的情况呢？步骤3 详细地说明了更新过程。

3．首先在 sumMap 中加入一个记录 (0,0)，它表示累加和 0 不用包括任何节点就可以得到。然后按照二叉树先序遍历的方式遍历节点，遍历到的当前节点记为 cur，从 head 到 cur 父节点的累加和记为 preSum，cur 所在的层数记为level。将 cur.value+preSum 的值记为 curSum，就是从 head 到 cur 的累加和。

• 如果 sumMap 中已经包含 curSum 的记录，则说明 curSum 在上层中已经出现过，那么就不更新sumMap；
• 如果 sumMap 不包含 curSum 的记录，则说明curSum 是第一次出现，就把（curSum,level）这个记录放入sumMap

接下来是求解在必须以 cur 结尾的情况下，累加和为规定值的最长路径长度，详细过程这里不再详述，请读者阅读“求未排序数组中累加和为规定值的最长子数组长度”问题。然后是遍历 cur 左子树和右子树的过程，依然按照上述方法使用和更新 sumMap。处理完以cur 为头节点的子树，当然要返回 cur 父节点。

在返回前还有一项重要的工作要做，在 sumMap 中查询 curSum 这个累加和（key）出现的层数（value）

• 如果 value 等于 level，则说明 curSum 这个累加和的记录是在遍历到 cur 时加上去的，那就把这条记录删除，目的是 保证 maxLen 在递归调用返回时不被污染，以便后续调用继续使用
• 如果 value 不等于 level，则不做任何调整。

4．步骤3 会遍历二叉树所有的节点，也会求解以每个节点结尾的情况下，累加和为规定值的最长路径长度。用 maxLen 记录其中的最大值即可。

代码

全部求解过程请参看如下代码中的 getMaxLength 方法。

package chapter_3_binarytreeproblem;import java.util.HashMap;public class Problem_06_LongestPathSum {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static int getMaxLength(Node head, int sum) {HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();sumMap.put(0, 0); // importantreturn preOrder(head, sum, 0, 1, 0, sumMap);}/*** 前序遍历，返回满足要求的累加和sum的最长路径* @param head 当前头结点* @param sum 指定的累加和* @param preSum 从head到cur父节点的累加和记为preSum* @param level cur所在的层数* @param maxLen 累加和等于sum的最长路径长度* @param sumMap (key, value) = (累加和, 累加和在路径中最早出现的层数)* @return*/public static int preOrder(Node head, int sum, int preSum, int level, int maxLen, HashMap<Integer, Integer> sumMap) {if (head == null) {return maxLen;}int curSum = preSum + head.value;if (!sumMap.containsKey(curSum)) { // curSum在上层未出现过，则记录sumMap.put(curSum, level); // sumMap中存放的，均为从二叉树【头结点】开始计算的累加和}if (sumMap.containsKey(curSum - sum)) { // 如果为true，说明从key所在位置到cur位置的累加和正好为sum// 此步骤求 "以cur结尾的情况下，满足累加和为sum的最长路径" 的长度// 即，将新的 "从key所在位置到cur位置的路径长度" 与 "到达此节点前，已经求得的最长路径长度" 相比较，取较大者maxLen = Math.max(level - sumMap.get(curSum - sum), maxLen);}maxLen = preOrder(head.left, sum, curSum, level + 1, maxLen, sumMap); // 递归前序遍历左子树maxLen = preOrder(head.right, sum, curSum, level + 1, maxLen, sumMap); // 递归前序遍历右子树if (level == sumMap.get(curSum)) { // 如果表中curSum这个累加和的记录是在遍历到cur时加上去的，则删除这条记录// 这样做的目的是：保证函数返回后sumMap不受到污染// 因为递归调用返回到上层函数后，后续可能还有preOrder()调用，还要用到sumMap// (可以类比"求所有排列组合"题目，也是需要在交换两元素后、返回前，恢复原状)sumMap.remove(curSum);}return maxLen;}// for test -- print treepublic static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {Node head = new Node(-3);head.left = new Node(3);head.right = new Node(-9);head.left.left = new Node(1);head.left.right = new Node(0);head.left.right.left = new Node(1);head.left.right.right = new Node(6);head.right.left = new Node(2);head.right.right = new Node(1);printTree(head);System.out.println(getMaxLength(head, 6));System.out.println(getMaxLength(head, -9));System.out.println(getMaxLength(head, 9));}}

总结

以上是生活随笔为你收集整理的左神算法：在二叉树中找到累加和为指定值的最长路径长度（Java版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。