二叉树结点间的最大距离问题

  • 递归
  • 改进的写法
  • 完整测试代码

题目

image.png

递归

解析
这个也是一个二叉树的问题，分为三步:

  • 列出所有可能性；
  • 列出结点需要的信息，并整合信息(成一个结构体)；
  • 改递归 ，先假设左和右都给我信息(黑盒)，然后怎么利用左边和右边的信息组出来我该返回的信息，最后basecase(边界)填什么；

具体到这个题目:
第一步，列出可能性： 一个以node为头的树上，最大距离只可能来自下面三种情况:

  • 不需要经过node这个点，node的左子树上自己的最大距离；
  • 不需要经过node这个点，node的右子树上自己的最大距离；
  • 要经过node这个点，此时就是左子树的高度 +右子树的高度+ 1；

第二步，确定结点需要的信息，并整合:

  • 信息一: 返回的以node为头的树的最大距离；
  • 信息二: 返回的以node为头的高度；

第三步，封装信息，写出递归

  1. public class Main {
  3.     static class Node {
  4.         public int value;
  5.         public Node left;
  6.         public Node right;
  8.         public Node(int value) {
  9.             this.value = value;
  10.         }
  11.     }
  13.     static class Pair {
  14.         public int max;
  15.         public int h;
  17.         public Pair(int max, int h) {
  18.             this.max = max;
  19.             this.h = h;
  20.         }
  21.     }
  23.     static int maxDistance(Node head) {
  24.         return rec(head).max;
  25.     }
  27.     static Pair rec(Node head) {
  28.         if (head == null)
  29.             return new Pair(0, 0);
  30.         Pair L = rec(head.left);
  31.         Pair R = rec(head.right);
  32.         return new Pair(Math.max((L.h + R.h + 1), Math.max(L.max, R.max)),
  33.                 Math.max(L.h, R.h) + 1);
  34.     }
  36. }

改进的写法

可以使用一个全局变量记录高度，然后max正常返回: 注意在java中要使用数组，是引用，这样的话就可以一直传递，不能使用一个变量

  1.     static int maxDistance2(Node head) {
  2.         int[] rec = new int[1];
  3.         return rec2(head, rec);
  4.     }
  6.     static int rec2(Node head, int[] rec) {
  7.         if (head == null) {
  8.             rec[0] = 0;
  9.             return 0;
  10.         }
  11.         int L = rec2(head.left, rec);
  12.         int lH = rec[0];
  13.         int R = rec2(head.right, rec);
  14.         int rH = rec[0];
  15.         rec[0] = Math.max(lH, rH) + 1;
  16.         return Math.max(lH + rH + 1, Math.max(L, R));
  17.     }

完整测试代码

  1. public class MaxDistance {
  3.     static class Node {
  4.         public int value;
  5.         public Node left;
  6.         public Node right;
  8.         public Node(int value) {
  9.             this.value = value;
  10.         }
  11.     }
  13.     static class Pair {
  14.         public int max;
  15.         public int h;
  17.         public Pair(int max, int h) {
  18.             this.max = max;
  19.             this.h = h;
  20.         }
  21.     }
  23.     static int maxDistance(Node head) {
  24.         return rec(head).max;
  25.     }
  27.     static Pair rec(Node head) {
  28.         if (head == null) {
  29.             return new Pair(0, 0);
  30.         }
  31.         Pair L = rec(head.left);
  32.         Pair R = rec(head.right);
  33.         return new Pair(Math.max((L.h + R.h + 1), Math.max(L.max, R.max)), Math.max(L.h, R.h) + 1);
  34.     }
  37.     static int maxDistance2(Node head) {
  38.         int[] rec = new int[1];
  39.         return rec2(head, rec);
  40.     }
  42.     static int rec2(Node head, int[] rec) {
  43.         if (head == null) {
  44.             rec[0] = 0;
  45.             return 0;
  46.         }
  47.         int L = rec2(head.left, rec);
  48.         int lH = rec[0];
  49.         int R = rec2(head.right, rec);
  50.         int rH = rec[0];
  51.         rec[0] = Math.max(lH, rH) + 1;
  52.         return Math.max(lH + rH + 1, Math.max(L, R));
  53.     }
  55.     static Node build(int[] arr, int index) {
  56.         if (index >= arr.length || arr[index] == -1)
  57.             return null;
  58.         Node root = new Node(arr[index]);
  59.         root.left = build(arr, index * 2 + 1);
  60.         root.right = build(arr, index * 2 + 2);
  61.         return root;
  62.     }
  64.     static void printTree(Node head, int height, String to, int len) {
  65.         if (head == null) return;
  66.         printTree(head.right, height + 1, "v", len);
  67.         String val = to + head.value + to;  //两边指示的字符
  68.         int lenV = val.length();
  69.         int lenL = (len - lenV) / 2;  //左边的空格(分一半)
  70.         int lenR = len - lenV - lenL; // 右边的空格
  71.         System.out.println(getSpace(len * height) + getSpace(lenL) + val + getSpace(lenR));
  73.         printTree(head.left, height + 1, "^", len);
  74.     }
  76.     //获取指定的空格
  77.     static String getSpace(int len) {
  78.         StringBuffer str = new StringBuffer();
  79.         for (int i = 0; i < len; i++) str.append(" ");
  80.         return str.toString();
  81.     }
  83.     public static void main(String[] args) {
  84.         int[] arr = {1, 2, 3, 4, 5, 6, 7};
  85.         Node head = build(arr, 0);
  86.         printTree(head, 0, "H", 10);
  87.         System.out.println(maxDistance(head));
  88.         System.out.println(maxDistance2(head));
  89.     }
  90. }

运行结果:(打印二叉树见这个博客)

image.png