二叉树的直径

解题思路：递归遍历，路径长度等于经过的节点个数减1（中间线的条数）。每个节点有两种选择，要么是作为中间节点，加入到别的路径；要么是作为根结点，形成新的路径。（注意，题目要求，路径不一定要穿过根结点）。

维护一个最优解，在每遍历到一个节点的时候，确定是否更新当前路径的最大长度。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }
    public int depth(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int depL = depth(node.left);
        int depR = depth(node.right);
        max = Math.max(max, depL+depR);//重新选择/确认根结点
        return Math.max(depL, depR) + 1; 
    }
}

上面是直接按走过的线的条数计算的，也可以按节点个数减一计算，如下：

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0; 
        int L = depth(node.left); 
        int R = depth(node.right);
        ans = Math.max(ans, L+R+1);
        return Math.max(L, R) + 1;
    }
}