二叉树的直径

leetCode–543（二叉树的直径）

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

示例 :
给定二叉树

      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 {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        return getCount(root.left) + getCount(root.right);
    }
    public int getCount(TreeNode root){
        if (root==null) return 0;
        int l = getCount(root.left);//左节点为根子树的深度
        int r =  getCount(root.right);//右节点为根子树的深度
        res = Math.max(res,l+r+1);//计算距离，保留计算过的最大值
        return Math.max(l,r)+1;//返回该节点为根的子树的深度
    }
}

但测试用例

[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

这个没有通过，感觉也没有毛病呀！

啊~看题解的解释才明白，题目中说的是，任意两个节点之间的距离，每个节点都可以当作根节点，所以要记录一下所求每个节点为根节点时，左右子树的最大深度和。才是最终的值。

代码为：

/**
 * 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 {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getCount(root);
        return res;
    }
    public int getCount(TreeNode root){
        if (root==null) return 0;
        int l = getCount(root.left);//左节点为根子树的深度
        int r =  getCount(root.right);//右节点为根子树的深度
        res = Math.max(res,l+r);//计算距离，保留计算过的最大值
        return Math.max(l,r)+1;//返回该节点为根的子树的深度
    }
}