543. 二叉树的直径

定义一个全局变量 maxDiameter 来记录和更新目前找到的最大直径。
设计一个递归函数 dfs(node)，它的核心任务有两个：
- 计算和更新直径：在当前节点，利用其左右子树的深度（通过递归获得）计算穿过当前节点的路径长度 (左深度 + 右深度)，并用此值更新 maxDiameter。
- 返回当前节点的深度：函数必须返回以当前节点为根的子树的深度 (1 + Math.max(左深度, 右深度))。这个返回值是提供给其父节点，作为父节点计算的“原材料”。

通过这种方式，递归从下至上返回深度的同时，我们在每一层都完成了对直径的计算和更新，从而保证了最终结果的正确性。

代码实现

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    // 用于记录和更新遍历过程中发现的最大直径。
    let maxDiameter = 0;

    /**
     * 深度优先搜索辅助函数
     * @param {TreeNode} node - 当前节点
     * @returns {number} - 返回以当前节点为根的子树的最大深度（边数）
     */
    const dfs = (node) => {
        // 基线条件：如果节点为空，其深度为 0。
        if (node === null) {
            return 0;
        }

        // 后序遍历：先递归计算左、右子树的最大深度。
        const leftDepth = dfs(node.left);
        const rightDepth = dfs(node.right);

        // 核心：计算穿过当前节点的路径长度，并更新全局最大直径。
        // 路径长度 = 左子树深度 + 右子树深度。
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 核心：返回当前节点的深度，供其父节点使用。
        // 节点深度 = 1 (当前节点到子节点的一条边) + 左右子树中较大的深度。
        return 1 + Math.max(leftDepth, rightDepth);
    };

    // 从根节点开始深度优先搜索。
    dfs(root);

    // 遍历完成后，maxDiameter 即为所求的答案。
    return maxDiameter;
};

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var diameterOfBinaryTree = function(root) { // 用于记录和更新遍历过程中发现的最大直径。 let maxDiameter = 0; /** * 深度优先搜索辅助函数 * @param {TreeNode} node - 当前节点 * @returns {number} - 返回以当前节点为根的子树的最大深度（边数） */ const dfs = (node) => { // 基线条件：如果节点为空，其深度为 0。 if (node === null) { return 0; } // 后序遍历：先递归计算左、右子树的最大深度。 const leftDepth = dfs(node.left); const rightDepth = dfs(node.right); // 核心：计算穿过当前节点的路径长度，并更新全局最大直径。 // 路径长度 = 左子树深度 + 右子树深度。 maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth); // 核心：返回当前节点的深度，供其父节点使用。 // 节点深度 = 1 (当前节点到子节点的一条边) + 左右子树中较大的深度。 return 1 + Math.max(leftDepth, rightDepth); }; // 从根节点开始深度优先搜索。 dfs(root); // 遍历完成后，maxDiameter 即为所求的答案。 return maxDiameter; };