根据题目意思，实际上我们计算出左右子树的高度相加后即为结果（实际还需-1）

1.深度优先遍历

时间O(n)，空间O(h)

class Solution {
    int max= 0;
    public int diameterOfBinaryTree(TreeNode root) {
        def(root);
        // 2点间的距离为1，此处计算结果为节点数，需做-1操作
        return max-1;
    }

    public int def(TreeNode root) {
        if (root==null) return 0;
        // 分别计算出左右子树的高低
        int left = def(root.left);
        int right = def(root.right);
        max = Math.max(left+right+1,max);
        // 返回当前root整颗字数的高度
        return Math.max(left,right)+1;
    }
}

 

2.广度优先遍历

参考之前计算二叉树最高深度的问题，此处分别计算出左右子树的高度后相加即可