08、二叉树的递归套路-最大距离

08、二叉树的递归套路-最大距离

题目：

给定一个二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离。

 1、解决方案1 1.1、思路：

1、先序遍历该树，依次存放到集合中
2、填充hashMap，key为当前节点，value为当前节点的父节点
3、暴力尝试两两节点之间的距离，取最大值

1.2、代码：

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

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

//方案1：暴力尝试
public static int maxDistance1(Node head) {
    if (head == null) {
        return 0;
    }
    //得到该树的所有节点（先序遍历）
    ArrayList arr = getPrelist(head);
    //填充hashMap
    //key：当前节点，value：当前节点的父节点
    HashMap parentMap = getParentMap(head);
    int max = 0;
    //暴力尝试两两节点之间的距离，取最大值
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            //求两个节点之间的距离
            int distance = distance(parentMap, arr.get(i), arr.get(j));
            max = Math.max(max, distance);
        }
    }
    return max;
}

//得到该树的所有节点（先序遍历）
public static ArrayList getPrelist(Node head) {
    ArrayList arr = new ArrayList<>();
    fillPrelist(head, arr);
    return arr;
}

//先序遍历该树，然后把节点加入到集合中
public static void fillPrelist(Node head, ArrayList arr) {
    if (head == null) {
        return;
    }
    arr.add(head);
    fillPrelist(head.left, arr);
    fillPrelist(head.right, arr);
}

//key：当前节点。value：当前节点的父亲节点
public static HashMap getParentMap(Node head) {
    HashMap map = new HashMap<>();
    map.put(head, null);
    fillParentMap(head, map);
    return map;
}

//填充hashMap
//key：当前节点，value：当前节点的父节点
public static void fillParentMap(Node head, HashMap parentMap) {
    if (head.left != null) {
        parentMap.put(head.left, head);
        fillParentMap(head.left, parentMap);
    }
    if (head.right != null) {
        parentMap.put(head.right, head);
        fillParentMap(head.right, parentMap);
    }
}


public static int distance(HashMap parentMap, Node o1, Node o2) {
    HashSet o1Set = new HashSet<>();
    Node cur = o1;
    o1Set.add(cur);
    //一直求解o1节点的父亲节点，放入到set集合中，直接父亲节点为空
    while (parentMap.get(cur) != null) {
        cur = parentMap.get(cur);
        o1Set.add(cur);
    }
    cur = o2;
    while (!o1Set.contains(cur)) {
        cur = parentMap.get(cur);
    }
    //找到了o1和o2的最低公共祖先
    Node lowestAncestor = cur;
    cur = o1;
    //求解o1到最低公共祖先的距离
    int distance1 = 1;
    while (cur != lowestAncestor) {
        cur = parentMap.get(cur);
        distance1++;
    }
    cur = o2;
    //求解o2到最低公共祖先的距离
    int distance2 = 1;
    while (cur != lowestAncestor) {
        cur = parentMap.get(cur);
        distance2++;
    }
    return distance1 + distance2 - 1;
}

 2、解决方案2 2.1、思路：

1、向左右子树分别要信息
2、返回左子树最大距离以及当前子树最大高度
3、返回右子树最大距离以及当前子树最大高度
4、最后根据信息来判断

2.2、代码：

//方案2：
public static int maxDistance2(Node head) {
    return process(head).maxDistance;
}

public static class Info {
    //以该节点为头的子树，节点之间最大距离是多少
    public int maxDistance;
    //以该节点为头的子树的高度
    public int height;

    public Info(int dis, int h) {
        maxDistance = dis;
        height = h;
    }
}

public static Info process(Node head) {
    if (head == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(head.left);
    Info rightInfo = process(head.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    //如果和head无关，那么此时最大距离就是取左树最大距离和右树最大距离中的最大值
    //如果和head有关，那么此时最大距离就是取左树高度加上右树高度，最后加上1
    int lrMaxDistance = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);
    int maxDistance = Math.max(lrMaxDistance, leftInfo.height + rightInfo.height + 1);
    return new Info(maxDistance, height);
}