# Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree.

# Example

Example 1:

Given a binary tree 
          1
         / \
        2   3
       / \     
      4   5    
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input:[2,3,#,1]
Output:2

Explanation:
      2
    /
   3
 /
1

# Solution

time complexity : O(n)
Space complexity: O(h)

最長距離也就是說可以計算兩點相鄰的邊
只有一個點是同時有左和右孩子。

Node from Lintcode:
最长路径有两种情况：
1. 最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。
2. 最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，
自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。

==

/**

 * Definition of TreeNode:

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left, right;

 *     public TreeNode(int val) {

 *         this.val = val;

 *         this.left = this.right = null;

 *     }

 * }

 */

public class Solution {

    /**

     * @param root: a root of binary tree

     * @return: return a integer

     */

     int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        maxDepth(root);

        return max;

    }

    private int maxDepth(TreeNode root){

        if (root == null) return 0;

        int left = maxDepth(root.left);

        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;

    }

}