二叉树的直径

543.二叉树的直径

题意

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

思路

转化一下：

所谓二叉树的直径，就是根节点的左右子树的最大深度之和，即左子树最深节点和右子树最深节点的距离。

那么就是对每个节点计算左右子树的最大高度，得出每个节点的直径，顺便更新最大直径，递归返回即可。

代码

class Solution {
    int ans = 0;

    int dfs(TreeNode root) {
        if (root == null) return 0;

        int l = dfs(root.left);
        int r = dfs(root.right);
        ans = Math.max(ans, l + r);  // 更新最长路径

        // 返回该节点的最大深度
        return Math.max(l, r) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
}