Description

算法步骤

链的定义：从子树中的叶子节点到当前节点的路径长度。

核心思路：

1. 遍历每个节点，计算以该节点为根的子树的最大链长
2. 对于每个节点，计算左子树和右子树的最大链长
3. 当前节点的最大链长 = max(左子树链长, 右子树链长) + 1
4. 更新全局最大直径 = max(全局最大直径, 左子树链长 + 右子树链长)

DFS函数说明：dfs(node) 返回以当前节点为根的子树的最大链长，不包含当前节点到父节点的边。

示例树结构：

                 1
   dfs(l)+1     / \    dfs(r)+1
               2   3
              / \   \
             4   5   6
Copy

链长计算过程：

• 节点4：链长 = 0（叶子节点）
• 节点5：链长 = 0（叶子节点）
• 节点6：链长 = 0（叶子节点）
• 节点2：链长 = max(0, 0) + 1 = 1
• 节点3：链长 = 0 + 1 = 1
• 节点1：链长 = max(1, 1) + 1 = 2

直径计算：

• 以节点1为根的直径 = 左子树链长(1) + 右子树链长(1) = 2
• 以节点2为根的直径 = 左子树链长(0) + 右子树链长(0) = 0
• 全局最大直径 = 2

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * val: number
 * left: TreeNode | null
 * right: TreeNode | null
 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 * }
 */

function diameterOfBinaryTree(root: TreeNode | null): number {
  let ans: number = 0;
  function dfs(node: TreeNode | null): number {
    if (!node) {
      return -1;
    }

    const left = dfs(node.left);
    const right = dfs(node.right);

    ans = Math.max(ans, left + right + 2); // 左子树最大链长+1，就是加上左子树到当前节点的边，右子树最大链长+1，就是加上右子树到当前节点的边。两条链拼成路径，更新最大值

    return Math.max(left, right) + 1;// 当前子树的左右子树最大链长加上当前节点到子树的边就是当前子树的最大链长
  }

  dfs(root);

  return ans;
};
Copy