543. 二叉树的直径

[Geekhyt]

原题链接

递归 dfs

• 一棵二叉树的直径长度是任意两个结点路径长度中的最大值
• 这条路径可能穿过也可能不穿过根结点

两个公式：

1. 最长路径 = 左子树最长路径 + 右子树最长路径 + 1 (根结点)
2. 高度(最大深度) = 左右子树中的最大深度 + 1 (根结点)

const diameterOfBinaryTree = function(root) {
    let ans = 1
    function depth(node) {
        if (node === null) return 0
        let L = depth(node.left)
        let R = depth(node.right)
        ans = Math.max(ans, L + R + 1)
        return Math.max(L, R) + 1 
    }
    depth(root)
    return ans - 1
}

• 时间复杂度: O(n)
• 空间复杂度: O(H)，H 为二叉树的高度