1、解决方案1 1.1、思路:题目:
给定一个二叉树的头节点head,任何两个节点之间都存在距离,返回整棵二叉树的最大距离。
1.2、代码:1、先序遍历该树,依次存放到集合中
2、填充hashMap,key为当前节点,value为当前节点的父节点
3、暴力尝试两两节点之间的距离,取最大值
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; } //得到该树的所有节点(先序遍历) ArrayList2、解决方案2 2.1、思路: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、代码:1、向左右子树分别要信息
2、返回左子树最大距离以及当前子树最大高度
3、返回右子树最大距离以及当前子树最大高度
4、最后根据信息来判断
//方案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); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)