左神算法笔记——二叉树最长路径累加和

题目

给定一棵二叉树的头节点head，和一个整数sum，二叉树每个节点上都有数字，我们规定路径必须是从上往下的，求二叉树上累加和为sum的最长路径长度。

分析

• 这题首先必须考虑到累加和为sum的路径有两种情况，可能是从根节点开始累加的，也有可能是从某一个子节点开始累加的。
• 所以这题的递归思路一定要考虑清楚边界条件和返回值。
• 因为不一定从根节点开始累加，所以我们必须从根节点一直遍历到子节点为null，而要求的参数maxLen（最大长度）可以作为回溯体中一个不断更新的变量，用作最终输出。
• 将从根节点开始的每一层的累加和都存储在一个Hashmap中，如果从根节点一直向下走到某个节点的累加和为curSum， 且curSum - sum在我们之前存储的每一层的累加和中出现过，那么此处就可以更新maxLen
• 最后一个非常关键的步骤，二叉树从上到下走到空节点的一条路径走完，返回上一层节点而选择走另一条路径时，必须前一个路径的根节点的键值对从map中移除。

代码

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

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

    /**
     * 求和为sum的最大路径长度
     * @param head
     * @param sum
     * @return
     */
    public static int getMaxLength(Node head, int sum) {
        HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
        sumMap.put(0, 0); // important, 0层累加和为0
        return preOrder(head, sum, 0, 1, 0, sumMap);
    }

    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)) {
            sumMap.put(curSum, level);
        }
        if (sumMap.containsKey(curSum - sum)) {   // 更新最大的长度
            // 更新最大的长度
            // 初始化扔了一个0，0在里面，所以如果有从根节点开始的累加和为sum,那么curSum-sum = 0,肯定在map里面，更新当前的level-0;
            // 如果当前的累加和超过了sum，那么其实递归不会在这里结束，会继续向下执行，一直走到节点为null时，返回当前的maxLen
            // 所以当累加和超过sum时，就会检查map中是否存在curSum - sum 的键值对，他的含义就是这条链起始位置不是根节点
            maxLen = Math.max(level - sumMap.get(curSum - sum), maxLen);
        }
        maxLen = preOrder(head.left, sum, curSum, level + 1, maxLen, sumMap);  // 向左进入递归，求maxLen
        maxLen = preOrder(head.right, sum, curSum, level + 1, maxLen, sumMap); // 再向右进入递归，这里会将左递归出来maxLen扔进去，不做计算，只用作比较
        // 这一步的目的就是保证当前map中的存放的键值对，都可以走到当前点的位置
        if (level == sumMap.get(curSum)) {
            sumMap.remove(curSum);
        }
        // 返回结果
        return maxLen;
    }

    // for test -- print tree(左神提供的二叉树直观呈现)
    public 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, 4));
        System.out.println(getMaxLength(head, 9));
    }

补充

对从SumMap中移除curSum的理解

        // 这一步的目的就是保证当前map中的存放的键值对，都可以走到当前点的位置
        if (level == sumMap.get(curSum)) {
            sumMap.remove(curSum);
        }

• 举实例说明，分析递归遍历过程