https://leetcode-cn.com/problems/longest-univalue-path/

二叉树的递归套路

  • 与x无关

    左右子树的max去pk一下

  • 与x有关

    • 1）x自己
    • 2）x 连同左树
    • 3）x 连同右树
    • 4）x连同左树和右树
  1.  public int longestUnivaluePath(TreeNode root) {
  2.      if (root == null) {
  3.          return 0;
  4.      }
  5.      return process(root).max - 1;
  6.  }
  8. public class Info {
  9.     public int len; // 路径必须以x为开头且只能往下走的情况下，路径的最大距离
  10.     public int max; // 路径不要求必须从x出发的情况下，整棵树的合法路径的最大距离
  12.     public Info(int l, int m) {
  13.         len = l;
  14.         max = m;
  15.     }
  16. }
  18. private Info  process(TreeNode x) {
  19.     if (x == null) {
  20.         return new Info(0, 0);
  21.     }
  22.     TreeNode l = x.left;
  23.     TreeNode r = x.right;
  24.     Info lInfo = process(l);
  25.     Info rInfo = process(r);
  26.     // x自己
  27.     int len = 1;
  28.     if (l != null && x.val == l.val) {
  29.         len = lInfo.len + 1;
  30.     }
  31.     if (r != null && x.val == r.val) {
  32.         len = Math.max(len, rInfo.len + 1);
  33.     }
  34.     // 这一句代码就把5种情况pk了一下
  35.     int max = Math.max(Math.max(lInfo.max, rInfo.max), len);
  36.     if (l != null && r != null && x.val == l.val && x.val == r.val) {
  37.         max = Math.max(max, lInfo.len + rInfo.len + 1);
  38.     }
  39.     return new Info(len, max);
  40. }