543. [✔][E]二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 : 给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

---

题解：

二叉树遍历框架

【HOT 100】9.二叉树的直径 Python3 递归也需要看清题意

// @ts-ignore
function diameterOfBinaryTree(root: TreeNode | null): number {
    let max = 0;

    // @ts-ignore
    const traverse = (root: TreeNode | null) => {
        if (root === null) {
            return 0;
        }

        let leftMax = traverse(root.left);
        let rightMax = traverse(root.right);

        // 二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径
        // 任意一个结点，都要记录以此结点为根的直径情况：左子树高度+右子树高度
        max = Math.max(max, leftMax + rightMax);

        // 注意，这里返回的是当前root节点的高度，最底层节点高度为1
        // 当前root节点高度就等于最高的子节点再往上加一层
        return 1 + Math.max(leftMax, rightMax);
    }

    traverse(root);

    return max;
};
// @lc code=end