HHot 100C++ 图解

543. 二叉树的直径

简单 二叉树 3 帧动画 在力扣上做

一句话套路后序:过每个结点的直径=左高+右高

题目描述

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

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

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

 

示例 1:

输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2:

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

 

提示:

  • 树中节点数目在范围 [1, 104] 内
  • -100 <= Node.val <= 100

思路

时间O(n)
空间O(h)

思路

直径 = 某个结点的「左深 + 右深」(按边数)。

递归函数只返回「高度」,直径用引用参数在沿途更新 —— 这就是「一个返回值不够用」时的标准处理方式,Q124 完全同构。

易错

返回高度时是 1+max(l,r),而更新答案时是 l+r(边数),别写成 l+r+1。

图解

4 2 5 1 3
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp19 行
namespace lc0543 {
class Solution {
 public:
  int diameterOfBinaryTree(TreeNode* root) {
    int best = 0;
    height(root, best);
    return best;
  }

 private:
  static int height(TreeNode* n, int& best) {
    if (!n) return 0;
    int l = height(n->left, best);
    int r = height(n->right, best);
    best = max(best, l + r);  // 经过 n 的最长路径(边数)
    return 1 + max(l, r);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q543_diameter8 行
lc0543::Solution s;
TreeNode* a = buildTree({1, 2, 3, 4, 5});
CHECK_EQ(s.diameterOfBinaryTree(a), 3);  // 4-2-1-3 或 5-2-1-3
freeTree(a);
TreeNode* b = buildTree({1, 2, nullopt, 3, nullopt, 4, nullopt, 5});  // 斜链
CHECK_EQ(s.diameterOfBinaryTree(b), 4);
freeTree(b);
CHECK_EQ(s.diameterOfBinaryTree(nullptr), 0);

↑↓ 选择↵ 打开/ 随时唤起