Given a binary tree in which each node contains an integer number. The diameter is defined as the longest distance from one leaf node to another leaf node.The distance is the number of nodes on the path.

If there does not exist any such paths, return 0.

Examples

5

/ \

2 11

 /    \

6     14

The diameter of this tree is 4 (2 → 5 → 11 → 14)

Solution: 注意recursion返回值和最后返回结果的不同。因为是leaf to leaf，所以左右非空时才更新max

  int max = 0;
  public int diameter(TreeNode root) {
 //注意这个if判断是错的 
 //   if (root == null || root.left == null || root.right == null) {
 //     return 0;
 //   }
    helper(root);
    return max;
  }
  private int helper(TreeNode root) {
    if (root == null) {
      return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);
    if (left > 0 && right > 0) {
      max = Math.max(max, left + right + 1);
    }
    return Math.max(left, right) + 1;
  }