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

import org.omg.CORBA.INTERNAL;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    int curVal;
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int curVal, int val) {
        this.curVal = curVal;
        this.val = val;
        left = null;
        right = null;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception{
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int curVal = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);
            int val = Integer.valueOf(strArr[3]);

            if(!mp.containsKey(curVal)){
                mp.put(curVal, new TreeNode(curVal, val));
            }else {
                TreeNode node = mp.get(curVal);
                node.val = val;
                mp.put(curVal, node);
            }
            if(leftVal != 0){
                if(!mp.containsKey(leftVal)){
                    mp.put(leftVal, new TreeNode(leftVal, -1));
                }
                mp.get(curVal).left = mp.get(leftVal);
            }
            if(rightVal != 0){
                if(!mp.containsKey(rightVal)){
                    mp.put(rightVal, new TreeNode(rightVal, -1));
                }
                mp.get(curVal).right = mp.get(rightVal);
            }
        }
        TreeNode root = mp.get(rootVal);
        int k = Integer.valueOf(reader.readLine());
//        System.out.println(getLen(root, k));

        Map<Integer,Integer> sumCengMap = new HashMap<>();
        sumCengMap.put(0, 0); // 和为0，不使用任何节点
        System.out.println(dfs(root, k, sumCengMap, 0, 0, 0));
    }

    // dfs 回溯，一条路径走到底
    static int dfs(TreeNode root, int k, Map<Integer, Integer> sumCengMap, int preSum, int preCeng, int maxLen){
        if(root == null){
            return maxLen;
        }
        int curLevel = preCeng + 1;
        int curSum = preSum + root.val;
        if(!sumCengMap.containsKey(curSum)){
            sumCengMap.put(curSum, curLevel);
        }
        if(sumCengMap.containsKey(curSum - k)){
            maxLen = Math.max(maxLen, curLevel - sumCengMap.get(curSum - k));
        }
        maxLen = dfs(root.left, k, sumCengMap, curSum, curLevel, maxLen);
        maxLen = dfs(root.right, k, sumCengMap, curSum, curLevel, maxLen);
        // 是遍历到当前节点加的 sumCengMap.put(curSum, curLevel)
        if(curLevel == sumCengMap.get(curSum)){
            sumCengMap.remove(curSum);
        }
        return maxLen;
    }

    // 错我，这是按照层来的，没有考虑节点是要在一条路径上
    static int getLen(TreeNode root, int k){
        Map<Integer,Integer> mp = new HashMap<>();
        mp.put(0, 0); // 和为0，不使用任何节点
        int maxLen = 0;

        Queue<TreeNode> que = new LinkedList<>();
        Queue<Integer> queCeng = new LinkedList<>();
        Queue<Integer> queSum = new LinkedList<>();
        que.offer(root);
        queCeng.offer(1);
        queSum.offer(root.val);
        while (!que.isEmpty()){
            TreeNode node = que.poll();
            int ceng = queCeng.poll();
            int sumPre = queSum.poll();
            if(mp.containsKey(sumPre - k)){
                int ans = ceng - mp.get(sumPre - k);
                maxLen = Math.max(maxLen, ans);
            }
            if(!mp.containsKey(sumPre)){
                mp.put(sumPre, ceng);
            }
            if(node.left != null) {
                que.offer(node.left);
                queCeng.offer(ceng + 1);
                queSum.offer(sumPre + node.left.val);
            }
            if(node.right != null) {
                que.offer(node.right);
                queCeng.offer(ceng + 1);
                queSum.offer(sumPre + node.right.val);
            }
        }
        return maxLen;
    }

}
/*
         1
     /        \
  2              3
 / \            /   \
4   5          6     7
    /\
   8  9

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
6

4

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
-9

1

35 29
29 26 32 -70
26 33 34 -19
33 0 0 31
34 0 0 -94
32 15 17 76
15 3 0 -28
3 0 11 32
11 24 0 -51
24 0 0 -92
17 18 30 55
18 22 21 -4
22 0 0 67
21 2 14 1
2 6 23 -92
6 0 8 74
8 0 0 65
23 0 9 85
9 16 0 43
16 0 12 -53
12 0 0 55
14 0 31 -68
31 35 0 -31
35 0 0 -17
30 0 4 29
4 19 10 8
19 0 28 34
28 25 0 -63
25 5 0 49
5 0 0 98
10 27 1 -88
27 20 0 52
20 7 13 50
7 0 0 -18
13 0 0 78
1 0 0 60
50

1
*/
ac
