【题目】
给定一棵二叉树的头节点head和一个32位整数sum，二叉树节点值类型为整型，求累加和为sum的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所组成的节点链。
package base;import java.util.HashMap;
import java.util.Map;public class P119_BtMaxLen {/*** 获取最长路径长度* @param head 头节点* @param k 指定值* @return*/public static int getMaxLen(Node head, int k) {Map<Integer, Integer> sumMap = new HashMap<Integer, Integer>();sumMap.put(0, 0);//重要return preOrder(head, k, 0, 1, 0, sumMap);}/*** 左子数和右子数 分别提供 最长路径* @param node* @param k* @param preSum 父节点累加和* @param level 节点层数* @param maxLen 最长路径* @param sumMap* @return*/public static int preOrder(Node node, int k, int preSum, int level, int maxLen, Map<Integer, Integer> sumMap) {if (node == null) {return maxLen;}int curSum = preSum + node.value;if (!sumMap.containsKey(curSum)) {sumMap.put(curSum, level);}if (sumMap.containsKey(curSum - k)) {maxLen = Math.max(level - sumMap.get(curSum - k), maxLen);}int leftMaxLen = preOrder(node.left, k, curSum, level + 1, maxLen, sumMap);int rightMaxLen = preOrder(node.right, k, curSum, level + 1, maxLen, sumMap);if (level == sumMap.get(curSum)) {sumMap.remove(curSum);// 当前节点返回上一层时，数据已无用，需要删除}return Math.max(leftMaxLen, rightMaxLen);}public static void main(String[] args) {Node node = new Node(-3);node.left = new Node(3);node.left.left = new Node(1);node.left.right = new Node(0);node.left.right.left = new Node(1);node.left.right.right = new Node(6);node.right = new Node(9);node.right.left = new Node(2);node.right.right = new Node(1);int maxLen = getMaxLen(node, 6);System.out.println(maxLen);}public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}
}