【LeetCode】二叉树的直径 [E]（二叉树）

543. 二叉树的直径 - 力扣（LeetCode）

一、题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

二、代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int diameterOfBinaryTree(TreeNode root) {return process(root).maxDistance - 1;}// 信息类public  class Info {// 当前树的最大距离public int maxDistance;// 当前树的高度public int height;public Info(int m, int h) {maxDistance = m;height = h;}}// 二叉树递归求解public Info process(TreeNode x) {// 如果是一个空树，那么这棵树的最大距离就是0，高度也是0      递归出口if (x == null) {// 这个就属于空置比较好处理的，所以就不向上返回null让上层去处理了，而是直接在本层创建好对应的info返回return new Info(0, 0);}// 左右子树向下递归   向下递归的位置// 递归返回左子树的infoInfo leftInfo = process(x.left);// 递归返回右子树的infoInfo rightInfo = process(x.right);// 当前树的告诉就是左右子树最大高度 + 1int height = Math.max(leftInfo.height, rightInfo.height) + 1;// 左树最大距离int p1 = leftInfo.maxDistance;// 右树最大距离int p2 = rightInfo.maxDistance;// 左树最大高度 + 右树最大高度 + 1int p3 = leftInfo.height + rightInfo.height + 1;// 当前树的最大距离就是p1、p2、p3中最大值int maxDistance = Math.max(Math.max(p1, p2), p3);// 创建当前树的info并返回       连接每一层递归的接口return new Info(maxDistance, height);}}

三、解题思路 

根据题意，列出来可能性。将这道题抽象成求以X为根节点的树的最大距离

可能性分类：1、最大距离与X无关   2、最大距离与X有关。

1、与X无关

也就是说X树上最大距离的路径是不通过X的，那么X树的最大距离就是X左子树最大距离和X右子树最大距离的最大值

2、与X有关

也就是说X树上最大距离的路径是通过X的，那么X树的最大距离就是 x左树离自己最远的点+ 1 +右树上离自己最远的点。即X左子树的高度 + X右子树的高度 + 1 就是X树的最大距离。

通过分类，我们就在知道在计算X树的最大距离是，应该需要其左右子树提供哪些信息，我们就知道了该如何对X左右子树提要求，进而设计info类。我们需要他们提供自己的高度和最大距离。