《程序员代码面试指南》第三章 二叉树问题 在二叉树中找见累加和为指定值的最长路径

题目

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

java代码

package com.lizhouwei.chapter3;


import java.util.HashMap;
import java.util.Map;

/**
 * @Description:在二叉树中找见累加和为指定值的最长路径
 * @Author: lizhouwei
 * @CreateDate: 2018/4/14 20:06
 * @Modify by:
 * @ModifyDate:
 */
public class Chapter3_6 {
    public int getMaxLength(Node head, int k) {
        if (head == null) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 0);
        return preOrder(head, 1, 0, 0, k, map);
    }

    public int preOrder(Node head, int level, int preValue, int maxLength, int k, Map<Integer, Integer> map) {
        if (head == null) {
            return maxLength;
        }
        int curValue = preValue + head.value;
        if (!map.containsKey(curValue)) {
            map.put(curValue, level);
        }
        if (map.containsKey(curValue - k)) {
            maxLength = Math.max(level - map.get(curValue - k), maxLength);
        }
        maxLength = preOrder(head.left, level + 1, curValue, maxLength, k, map);
        maxLength = preOrder(head.right, level + 1, curValue, maxLength, k, map);
        //在退出此节点时删除节点对应的值
        if (level == map.get(curValue)) {
            map.remove(curValue);
        }
        return maxLength;
    }

    //测试
    public static void main(String[] args) {
        Chapter3_6 chapter = new Chapter3_6();
        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.right.left = new Node(2);
        head.right.right = new Node(1);
        head.left.right.left = new Node(1);
        head.left.right.right = new Node(6);

        int res = chapter.getMaxLength(head, 6);
        System.out.print(res);
    }
}