二叉树的直径 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

视频讲解

本题视频讲解：树形 DP【基础算法精讲 23】，制作不易，欢迎点赞~

视频内容补充

设 $node$ 是二叉树中的一个节点。

本题有两个关键概念：

链：从 $node$ 子树中的叶子节点到 $node$ 的路径。把 $node$ 子树中的最长链的长度，作为 $dfs (node)$ 的返回值。
直径：等价于由两条（或者一条）链拼成的路径。我们枚举二叉树的每个 $node$ ，假设直径在这里「拐弯」，也就是计算由左右两条从下面的叶子节点到 $node$ 的链的节点值之和，去更新答案的最大值。

⚠注意：直径可能在 $root$ 下面的某个节点拐弯，不一定会经过 $root$ 。

⚠注意： $dfs (node)$ 返回的是链的长度，不是直径的长度。如果返回直径，那么在上面与其他的链继续拼接，得到的就不是直径了。

写法一

$dfs (node)$ 返回的是 $node$ 子树的最大链长，不包含 $node$ 到其父节点的边。如果严格按照这个定义，空节点要返回 $- 1$ ，这样叶子算出的链长才是 $0$ 。

如果你觉得这样写有些奇怪，可以看等价的写法二。

Python 解法1C++ 解法1

python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0

        # 返回 node 子树的最大链长
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return -1  # 对于叶子来说，链长就是 -1+1=0
            l_len = dfs(node.left) + 1  # 左子树最大链长+1
            r_len = dfs(node.right) + 1  # 右子树最大链长+1
            nonlocal ans
            ans = max(ans, l_len + r_len)  # 两条链拼成路径
            return max(l_len, r_len)  # 当前子树最大链长

        dfs(root)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;

        // 返回 node 子树的最大链长
        auto dfs = [&](this auto&& dfs, TreeNode* node) -> int {
            if (node == nullptr) {
                return -1; // 对于叶子来说，链长就是 -1+1=0
            }
            int l_len = dfs(node->left) + 1; // 左子树最大链长+1
            int r_len = dfs(node->right) + 1; // 右子树最大链长+1
            ans = max(ans, l_len + r_len); // 两条链拼成路径
            return max(l_len, r_len); // 当前子树最大链长
        };

        dfs(root);
        return ans;
    }
};

写法二

Python 解法3C++ 解法3

python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0

        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            l_len = dfs(node.left)
            r_len = dfs(node.right)
            nonlocal ans
            ans = max(ans, l_len + r_len)  # 两条链拼成路径
            return max(l_len, r_len) + 1

        dfs(root)
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;

        auto dfs = [&](this auto&& dfs, TreeNode* node) -> int {
            if (node == nullptr) {
                return 0;
            }
            int l_len = dfs(node->left);
            int r_len = dfs(node->right);
            ans = max(ans, l_len + r_len); // 两条链拼成路径
            return max(l_len, r_len) + 1;
        };

        dfs(root);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (h)$ ，其中 $h$ 是二叉树的高度。递归需要 $O (h)$ 的栈空间。

相似题目

见下面树题单的「§2.6 二叉树的直径」和「§3.5 树的直径」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

视频内容补充 ​

写法一 ​

写法二 ​

复杂度分析 ​

相似题目 ​

分类题单 ​

视频讲解

视频内容补充

写法一

写法二

复杂度分析

相似题目

分类题单