543. 二叉树的直径

一 题目：

二 思路：

• 分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度
• 我们只需要找出每一个节点的 左子树最大深度 + 右子树最大深度 的值，然后不断更新全局变量max 就行了

三 代码：

class Solution {
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        //分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度
        max=0;
        dfs(root);
        return max;
    }

    /**
     * 返回树的深度
     */
    private int dfs(TreeNode root) {
        if (root==null){
            return 0;
        }
        //左子树的深度
        int lDeep= dfs(root.left);
        //右子树的深度
        int rDeep= dfs(root.right);

        max=Math.max(max,lDeep+rDeep);
        return Math.max(lDeep,rDeep)+1;
    }
}