LeetCode 543. 二叉树的直径

Categories:

Tags:

题目描述
思路分析
1. 解法一：DFS 后序遍历（推荐）
相似题目

题目描述

✅ 543. 二叉树的直径

思路分析

解法一：DFS 后序遍历（推荐）

核心思路：

直径定义：二叉树中任意两节点的最长路径（边数），该路径不一定经过根节点。

关键洞察：每条路径必有一个”最高拐点”（路径从左子树向上经过该节点再向右子树延伸）。枚举每个节点作为拐点，其直径候选值 = 左子树深度 + 右子树深度。

后序遍历过程：递归先处理左右子树，得到 left（左子树最大深度）和 right（右子树最大深度），更新全局最大直径 res = max(res, left + right)，最后返回当前节点深度 max(left, right) + 1。

为什么用后序：需要先知道左右子树深度才能计算当前节点的直径贡献，后序（左→右→根）天然满足这一顺序。

与 124 题类比：结构完全相同，只是把”深度”换成”路径和”，负数需置 0。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，每个节点访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归栈深度

class Solution {
    // 全局变量维护最大直径
    private int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 后序：先递归左右子树，得到各自最大深度
        int left = dfs(node.left);
        int right = dfs(node.right);
        // 以当前节点为拐点，直径候选值 = 左深度 + 右深度
        res = Math.max(res, left + right);
        // 返回当前节点的最大深度（向上汇报）
        return Math.max(left, right) + 1;
    }
}

func diameterOfBinaryTree(root *TreeNode) int {
    // 全局变量维护最大直径
    var res int

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        // 后序：先递归左右子树，得到各自最大深度
        left := dfs(node.Left)
        right := dfs(node.Right)
        // 以当前节点为拐点，直径候选值 = 左深度 + 右深度
        if left+right > res {
            res = left + right
        }
        // 返回当前节点的最大深度（向上汇报）
        if left > right {
            return left + 1
        }
        return right + 1
    }

    dfs(root)
    return res
}

相似题目

题目	难度	考察点
124. 二叉树中的最大路径和	困难	DFS 后序遍历、全局最大值
687. 最长同值路径	中等	DFS 后序遍历、路径计数
1245. 树的直径	中等	BFS/DFS、图上直径
104. 二叉树的最大深度	简单	DFS 后序遍历求深度
110. 平衡二叉树	简单	DFS 后序遍历判平衡
979. 在二叉树中分配硬币	中等	DFS 后序遍历、贡献值统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83624487