跳到主要内容

LeetCode 543. 二叉树的直径

本节目标

返回可向上延伸的高度，并在每个节点更新经过该节点的最长边数。

这道题展示子树信息与递归判断中最重要的职责分离：递归向上返回高度，当前节点更新直径。

查看 LeetCode 原题

题意与边界​

直径是任意两节点之间最长路径的边数。空树直径为 0，只有一个节点时也为 0。最长路径未必经过根，因此不能只在根节点计算一次左右高度。

高度返回与直径更新​

diameterDfs(node) 仍只返回以 node 为根的最大高度，因为父节点只能从当前节点选择一条分支继续向上。当前节点处的候选直径则是左高度加右高度：两段路径分别以边连接到当前节点，恰好得到经过当前节点的边数。用独立答案记录所有节点的候选最大值，并在平台入口开始时重置它。

正确性依据​

任意简单路径都有唯一的最高节点。该路径经过这个节点时，分别落入其左、右子树（或一侧为空），长度正是两侧最大可延伸高度之和。递归访问每个节点并更新该候选值，因此全局答案不会漏掉最长路径；同时向父节点返回较长单边高度，保持了高度报告的正确语义。

代码实现​

C++17
#include <algorithm>

using namespace std;

class Solution {
private:
    int answer = 0;

    int diameterDfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        const int leftHeight = diameterDfs(node->left);
        const int rightHeight = diameterDfs(node->right);
        answer = max(answer, leftHeight + rightHeight);
        return max(leftHeight, rightHeight) + 1;
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        answer = 0;
        diameterDfs(root);
        return answer;
    }
};

复杂度分析​

每个节点只计算一次左右高度，时间复杂度为 O(n)。递归栈占用 O(h) 空间，答案只额外占用 O(1) 空间。

易错点​

  • 将 leftHeight + rightHeight + 1 当作答案，误把节点数当成边数。
  • 把左右高度之和返回给父节点，使父节点形成不连续的路径。
  • 多次调用同一个 C++ Solution 对象时没有重置保存的答案。

模式迁移​

最大路径和也会在当前节点组合左右信息，但向上只返回一侧贡献。遇到“当前节点更新完整答案、父节点只拿一部分信息”的题目，应先分开定义这两个量。