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

import java.io.*;
import java.util.*;
public class Main {

    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
        public Node(){

        }
    }

    public static int countLongest (Node head, int k) {
        //key表示某个累加和，value表示这个累加和在路径中最早出现层数
        HashMap<Integer, Integer> map = new HashMap<>();
        //表示不用包括任何节点就可以得到累加和为0
        map.put(0,0);
        return preOrder (head, k, map, 0, 1, 0);
    }

    public static int preOrder (Node head, int k, HashMap<Integer, Integer> map, int preSum, int level, int maxLen) {
        if (head == null) {
            return maxLen;
        }
        int curSum = preSum + head.value;
        if (!map.containsKey(curSum))
            map.put(curSum, level);
        if (map.containsKey(curSum-k)) {
            maxLen = Math.max(maxLen, level - map.get(curSum-k));
        }
        maxLen = preOrder(head.left, k, map, curSum, level + 1, maxLen);
        maxLen = preOrder(head.right, k, map, curSum, level + 1, maxLen);
        //跑到头来说明已经把一条能检测的路走到头了，此时该走另外一条路了，若不删除当前
        //新加进map里去的curSum和level，万一下一条路径有某个curSum-k恰好等于当前curSum
        //会误以为他们在同一条路径上，造成结果有误
        if (level == map.get(curSum))
            map.remove(curSum);
        return maxLen;
    }



    public static void main(String[] args) {
        HashMap<Integer,Node> map = new HashMap<Integer,Node>() ;
        Scanner in = new Scanner(System.in);

        String[] input = in.nextLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int rootID=Integer.parseInt(input[1]);
        Node root=new Node();
        map.put(rootID,root);   //root中暂且没有添加值

        for (int i = 0; i < n; i++) {
            //build the binary tree
            String[] nodes = in.nextLine().split(" ");
            int nodeID = Integer.parseInt(nodes[0]);
            int leftID = Integer.parseInt(nodes[1]);
            int rightID = Integer.parseInt(nodes[2]);
            int value=Integer.parseInt(nodes[3]);

            //遍历Map并添加ID，node
            if(map.containsKey(nodeID)){
                Node tempNode=map.get(nodeID);
                tempNode.value=value;   //添加node的值

                //添加左右节点
                Node leftNode = leftID == 0 ? null : new Node();
                Node rightNode = rightID == 0 ? null : new Node();
                tempNode.left = leftNode;
                tempNode.right = rightNode;

                //左右放入map
                if(leftID!=0){
                    map.put(leftID,leftNode);
                }
                if(rightID!=0){
                    map.put(rightID,rightNode);
                }
            }

        }

        int num=Integer.parseInt(in.nextLine());
        int result=countLongest (root,num);
        System.out.println(result);

    }
}