543. 二叉树的直径

力扣题目链接 (opens new window)

题目描述

给你一棵二叉树的根节点，返回该树的直径。直径是树中任意两个节点之间最长路径的长度，长度由路径上的边数表示。这条路径不一定经过根节点。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：路径 [4,2,1,3] 或 [5,2,1,3] 有 3 条边。

示例 2：

输入：root = [1,2]
输出：1

思路

最长路径可能不经过根节点，直接求根的左右高度够吗？不够，必须在每个节点处都计算一次“经过该节点的最长路径”。这条路径向左能走 leftHeight 条边，向右能走 rightHeight 条边，合起来就是 leftHeight + rightHeight。

高度怎么求？沿用104.二叉树的最大深度的后序遍历：空节点返回 0，当前节点返回 1 + max(左右高度)。在返回高度之前，顺便更新全局直径。注意返回给父节点的只能是一侧高度，因为父节点的路径不能在当前节点分叉。

模拟过程

以 [1,2,3,4,5] 为例：节点 4、5、3 的高度都是 1；节点 2 的左右高度各为 1，经过 2 的路径长 2；根节点 1 的左高度 2、右高度 1，经过 1 的路径长 3，最终答案为 3。

主站用下面这张树图讲过“从叶子向上返回高度”，计算直径时也按同样顺序处理：

解题代码

class Solution {
    int result = 0;
    int height(TreeNode* node) {
        if (node == nullptr) return 0;
        int left = height(node->left);
        int right = height(node->right);
        result = max(result, left + right); // 边数等于左右子树高度之和
        return 1 + max(left, right);        // 父节点只能延伸一侧
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        result = 0;
        height(root);
        return result;
    }
};

复杂度分析

• 时间复杂度：O(n)，每个节点只计算一次高度。
• 空间复杂度：O(h)，递归栈占用树高 h。

其他语言

Python3

class Solution:
    def diameterOfBinaryTree(self, root):
        result = 0
        def height(node):
            nonlocal result
            if node is None:
                return 0
            left, right = height(node.left), height(node.right)
            result = max(result, left + right)
            return 1 + max(left, right)
        height(root)
        return result

Java

class Solution {
    int result;
    int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left), right = height(node.right);
        result = Math.max(result, left + right);
        return 1 + Math.max(left, right);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        result = 0;
        height(root);
        return result;
    }
}

Go

func diameterOfBinaryTree(root *TreeNode) int {
    result := 0
    var height func(*TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil { return 0 }
        left, right := height(node.Left), height(node.Right)
        if left + right > result { result = left + right }
        if left > right { return left + 1 }
        return right + 1
    }
    height(root)
    return result
}

JS

var diameterOfBinaryTree = function(root) {
    let result = 0;
    function height(node) {
        if (node === null) return 0;
        const left = height(node.left), right = height(node.right);
        result = Math.max(result, left + right);
        return 1 + Math.max(left, right);
    }
    height(root);
    return result;
};

与代码随想录联系

主站目前没有 543 的独立题解；这道题沿用了104.二叉树的最大深度的后序求高度思路。录友需要额外记住：高度返回给父节点，直径在每个节点处更新。