二叉树的直径 - Stellar Observer Protocol

694 字

3 分钟

二叉树的直径

2025-08-16

Algorithms

树

/

深度优先搜索

/

二叉树

题目描述#

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

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

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

解题思路#

深度优先搜索：
- 后序遍历二叉树（左→右→根）
- 计算每个节点的左右子树高度
直径计算：
- 节点直径 = 左子树高度 + 右子树高度
- 更新全局最大直径
高度传递：
- 节点高度 = max(左高, 右高) + 1
- 返回给父节点用于计算
全局变量：
- 使用外部变量记录最大直径
- 遍历结束时返回该值

关键洞察#

直径本质：
- 最长路径 = 左最深叶子 → 节点 → 右最深叶子
- 可能不经过根节点
高度复用：
- 直径计算依赖子树高度
- 后序遍历自然获取高度信息
负高度处理：
- 空节点高度为0
- 叶子节点高度为1
全局更新时机：
- 每个节点计算后立即更新最大直径
- 确保不遗漏任何可能路径

复杂度分析#

指标	说明
时间复杂度	O(n)：每个节点访问一次
空间复杂度	O(h)：递归栈深度（h为树高，最坏O(n)）

代码实现#

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
var diameterOfBinaryTree = function (root) {
14
    let result = -Infinity;
15
    const dfs = (root) => {
16
        if (!root) return 0;
17
        const left = dfs(root.left);
18
        const right = dfs(root.right);
19
        result = Math.max(result, left + right);
20
        return Math.max(left, right) + 1
21
    }
22
    dfs(root);
23

24
    return result
25
};

1
use std::rc::Rc;
2
use std::cell::RefCell;
3
use std::cmp::max;
4

5
struct TreeNode {
6
    val: i32,
7
    left: Option<Rc<RefCell<TreeNode>>>,
8
    right: Option<Rc<RefCell<TreeNode>>>,
9
}
10

11
impl TreeNode {
12
    fn new(val: i32) -> Self {
13
        TreeNode {
14
            val,
15
            left: None,
16
            right: None,
17
        }
18
    }
19
}
20

21
fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
22
    let mut max_diameter = 0;
23

24
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
25
        match node {
26
            None => 0,
27
            Some(n) => {
28
                let n = n.borrow();
29
                let left_depth = dfs(&n.left, max_diameter);
30
                let right_depth = dfs(&n.right, max_diameter);
31
                *max_diameter = max(*max_diameter, left_depth + right_depth);
32
                max(left_depth, right_depth) + 1
33
            }
34
        }
35
    }
36

37
    dfs(&root, &mut max_diameter);
38
    max_diameter
39
}

1
class TreeNode:
2
    def __init__(self, val=0, left=None, right=None):
3
        self.val = val
4
        self.left = left
5
        self.right = right
6

7
def diameterOfBinaryTree(root: TreeNode) -> int:
8
    max_diameter = 0
9

10
    def dfs(node):
11
        nonlocal max_diameter
12
        if not node:
13
            return 0
14
        left_depth = dfs(node.left)
15
        right_depth = dfs(node.right)
16
        max_diameter = max(max_diameter, left_depth + right_depth)
17
        return max(left_depth, right_depth) + 1
18

19
    dfs(root)
20
    return max_diameter