尧图网站建设 
LeetCode-Go 题解精讲543. Diameter of Binary Tree 二叉树直径的后序遍历解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 543「二叉树的直径」Diameter of Binary Tree在开源仓库 LeetCode-Go可用git clone获取中的 Go 语言题解。直径是二叉树中任意两个节点之间最长路径的边数这道题是典型的「后序遍历 全局最大值」模板题也是104. 二叉树的最大深度的进阶变体。读完本文你将掌握如何把求最大深度的递归函数改造成边遍历边更新全局直径的写法理解时间复杂度 O(n) 与空间复杂度 O(h) 的推导并能直接用仓库中的测试用例验证答案。题目定义与理解原题描述给定一棵二叉树的根节点root返回这棵树的直径长度。直径被定义为树中任意两个节点之间最长路径的边数这条路径可能穿过根节点也可能不穿过根节点。题目原文位于 leetcode/0543.Diameter-of-Binary-Tree/README.md。需要特别留意三个关键点长度单位是边数而不是节点数直径3对应路径[4,2,1,3]其中包含4→2、2→1、1→3三条边如果把边数误当成节点数答案会整体偏大 1。路径不一定要经过根节点直径可能完全落在某个子树内部所以不能简单地用左子树深度 右子树深度一次算完必须在遍历过程中对每个节点都考察一次。示例数据root [1,2,3,4,5]→ 输出3即路径[4,2,1,3]或[5,2,1,3]root [1,2]→ 输出1即1与2之间只有一条边。数据范围节点数量范围[1, 104]节点值范围-100 Node.val 100。节点数量最大可达 10⁴说明递归深度最多约 10⁴ 层最坏情况是链状树Go 默认栈能够承受节点值允许为负数因此在实现中要小心不能用节点值参与任何与答案比较的运算——本题解只统计深度与Val完全无关。解题思路后序遍历 全局最大值核心思想树的直径一定可以表述为以某个节点为拐点取其左子树某节点到右子树某节点的最长路径路径长度 该节点左子树的最大深度 该节点右子树的最大深度两条边在该节点处汇合。因此对每个节点计算left right经过该节点的最长路径边数并用它更新全局最大值向父节点返回max(left, right) 1表示以该节点为端点、向下延伸的最长单侧深度。这一模式在数据结构教材中常称为边计算、边上传递归函数在后序位置左右子树都已算完完成两件事——更新全局答案、向上一层返回本节点能提供的最大深度。这也是为什么这道题经常与最大深度0104.Maximum-Depth-of-Binary-Tree归为一类模板题把深度题的返回值加上顺带更新全局最大值这一步就是直径题。图解推演示例[1,2,3,4,5]对应二叉树1 / \ 2 3 / \ 4 5后序遍历过程访问节点左子树深度 left右子树深度 right经过该节点的候选直径 leftright返回给父节点的深度4叶子00015叶子0001211223叶子000112133全局最大值在节点2处先被更新为2随后在根节点1处被更新为3最终答案为3。注意2号节点贡献的直径2虽然被根节点的3覆盖但在其它形态的树上例如右子树为空非根节点处的候选值可能就是最终答案这正是边遍历边更新的原因。复杂度分析时间复杂度O(n)每个节点恰好被访问一次递归体内只有常数次操作空间复杂度O(h)h 为树高取决于递归栈深度。最坏情况链状树为 O(n)平均/最好情况平衡树为 O(log n)。仓库源码实现逐行精讲核心代码位于 leetcode/0543.Diameter-of-Binary-Tree/543. Diameter of Binary Tree.go完整源码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func diameterOfBinaryTree(root *TreeNode) int { result : 0 checkDiameter(root, result) return result } func checkDiameter(root *TreeNode, result *int) int { if root nil { return 0 } left : checkDiameter(root.Left, result) right : checkDiameter(root.Right, result) *result max(*result, leftright) return max(left, right) 1 } func max(a int, b int) int { if a b { return a } return b }逐段解读type TreeNode structures.TreeNode类型别名直接复用仓库structures子包中定义的树节点结构避免每个题解目录重复定义。TreeNode的真实定义位于 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }diameterOfBinaryTree入口函数初始化result : 0调用checkDiameter后返回result。这里有一个容易忽略的细节result用指针传入递归函数因为 Go 语言中闭包或值传递都无法直接修改外层局部变量而指针可以让每一层递归共享同一个全局答案。checkDiameter递归核心递归出口root nil返回0空子树深度为 0后序遍历先递归左子树得left再递归右子树得right此时左右子树的深度信息已齐备更新全局答案*result max(*result, leftright)leftright表示以当前节点为路径拐点时跨过该节点的最长边数返回单侧深度return max(left, right) 1向父节点汇报从当前节点向下延伸的最长路径边数1表示当前节点到父节点之间的那条边。max辅助函数题解目录内自带的两个整数取大函数保持代码零外部依赖未使用math.Max因此也无需处理浮点转换。测试用例验证仓库为本题提供了完整测试位于 leetcode/0543.Diameter-of-Binary-Tree/543. Diameter of Binary Tree_test.go采用表驱动 数组转树的测试风格func Test_Problem543(t *testing.T) { qs : []question543{ { para543{[]int{1, 2, 3, 4, 5}}, ans543{3}, }, { para543{[]int{1, 2}}, ans543{1}, }, { para543{[]int{4, -7, -3, structures.NULL, structures.NULL, -9, -3, 9, -7, -4, structures.NULL, 6, structures.NULL, -6, -6, structures.NULL, structures.NULL, 0, 6, 5, structures.NULL, 9, structures.NULL, structures.NULL, -1, -4, structures.NULL, structures.NULL, structures.NULL, -2}}, ans543{8}, }, } ... for _, q : range qs { ... root : structures.Ints2TreeNode(p.one) fmt.Printf(【output】:%v \n, diameterOfBinaryTree(root)) } }三个测试点覆盖了不同形态[1,2,3,4,5]→3直径经过根节点即题目给出的 Example 1[1,2]→1只有一条边验证最简情形第三个长用例 →8这是一棵直径不经过根节点的复杂树包含structures.NULL空位标记与大量负值节点专门用来验证边遍历边更新全局最大值的正确性——若只计算左子树深度 右子树深度这个用例会得出错误答案。测试基础设施Ints2TreeNode 与 NULL测试中的structures.Ints2TreeNode和structures.NULL都来自 structures/TreeNode.goNULL被定义为var NULL -1 63structures/TreeNode.go即 int 类型的最小值用于在层序数组里标记空节点Ints2TreeNodestructures/TreeNode.go采用**层序遍历BFS**方式把[]int还原成二叉树先以第一个元素建根再用队列逐层挂载左右孩子遇到NULL标记则跳过该孩子。仓库中大量二叉树题解复用这一工具测试数据只需写层序数组无需手工构造指针。本地运行测试在仓库根目录执行以下命令即可验证依赖go 1.19模块定义见 go.mod# 只运行本题测试 go test -v ./leetcode/0543.Diameter-of-Binary-Tree/... # 运行全部 leetcode 题解测试并生成覆盖率 ./gotest.sh仓库的 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性生成合法的覆盖率文件这正是项目 README 中100% test coverage说法的由来coverage.txt位于仓库根目录可直接用 Codecov 等工具解析。边界情况与易错点直径单位是边数leftright本身就是边数子树深度以边计无需再加 1。若误用节点数答案为leftright1全部测试都会失败。路径可以不经过根必须在递归过程中对每个节点执行*result max(*result, leftright)不能只在根节点算一次。result必须用指针传递否则内层递归对result的修改在外层不可见最终返回的永远是0。空树与单节点题目约束节点数 1但函数对空树依然正确返回 0单节点树返回 0没有边这是直径的定义使然。max(left, right) 1的1不能丢它代表当前节点到父节点的那条边丢了会导致父节点拿到的深度少 1。与其他题解的关系本题是二叉树递归模板链条上承上启下的一环前置知识0104.Maximum-Depth-of-Binary-Tree最大深度checkDiameter的返回值部分正是最大深度题的解体同型题目0110.Balanced-Binary-Tree平衡二叉树同样使用后序位置计算左右子树高度并判断的模式0124.Binary-Tree-Maximum-Path-Sum二叉树中的最大路径和则是本题的加权变体——把边数之和换成节点值之和统一模式三者都是递归返回子树单向最优值 闭包/指针维护全局最优值理解本题即可举一反三。仓库内所有题解目录遵循统一组织方式每个题目一个目录内含题目名.go题解、题目名_test.go测试与README.md题面、思路、代码全部复用 structures 子包的基础数据结构方便横向对照阅读。总结直径 任意两节点间最长路径的边数可能不经过根节点解法模板后序遍历中对每个节点用leftright更新全局最大值向上返回max(left,right)1时间复杂度 O(n)、空间复杂度 O(h)与最大深度题同构仓库题解通过*result指针维护全局答案配套 3 组测试用例含直径不经过根节点的复杂用例验证正确性可在 leetcode/0543.Diameter-of-Binary-Tree 目录下直接运行测试复现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：543. Diameter of Binary Tree 二叉树直径的后序遍历解法
LeetCode-Go 题解精讲543. Diameter of Binary Tree 二叉树直径的后序遍历解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 543「二叉树的直径」Diameter of Binary Tree在开源仓库 LeetCode-Go可用git clone获取中的 Go 语言题解。直径是二叉树中任意两个节点之间最长路径的边数这道题是典型的「后序遍历 全局最大值」模板题也是104. 二叉树的最大深度的进阶变体。读完本文你将掌握如何把求最大深度的递归函数改造成边遍历边更新全局直径的写法理解时间复杂度 O(n) 与空间复杂度 O(h) 的推导并能直接用仓库中的测试用例验证答案。题目定义与理解原题描述给定一棵二叉树的根节点root返回这棵树的直径长度。直径被定义为树中任意两个节点之间最长路径的边数这条路径可能穿过根节点也可能不穿过根节点。题目原文位于 leetcode/0543.Diameter-of-Binary-Tree/README.md。需要特别留意三个关键点长度单位是边数而不是节点数直径3对应路径[4,2,1,3]其中包含4→2、2→1、1→3三条边如果把边数误当成节点数答案会整体偏大 1。路径不一定要经过根节点直径可能完全落在某个子树内部所以不能简单地用左子树深度 右子树深度一次算完必须在遍历过程中对每个节点都考察一次。示例数据root [1,2,3,4,5]→ 输出3即路径[4,2,1,3]或[5,2,1,3]root [1,2]→ 输出1即1与2之间只有一条边。数据范围节点数量范围[1, 104]节点值范围-100 Node.val 100。节点数量最大可达 10⁴说明递归深度最多约 10⁴ 层最坏情况是链状树Go 默认栈能够承受节点值允许为负数因此在实现中要小心不能用节点值参与任何与答案比较的运算——本题解只统计深度与Val完全无关。解题思路后序遍历 全局最大值核心思想树的直径一定可以表述为以某个节点为拐点取其左子树某节点到右子树某节点的最长路径路径长度 该节点左子树的最大深度 该节点右子树的最大深度两条边在该节点处汇合。因此对每个节点计算left right经过该节点的最长路径边数并用它更新全局最大值向父节点返回max(left, right) 1表示以该节点为端点、向下延伸的最长单侧深度。这一模式在数据结构教材中常称为边计算、边上传递归函数在后序位置左右子树都已算完完成两件事——更新全局答案、向上一层返回本节点能提供的最大深度。这也是为什么这道题经常与最大深度0104.Maximum-Depth-of-Binary-Tree归为一类模板题把深度题的返回值加上顺带更新全局最大值这一步就是直径题。图解推演示例[1,2,3,4,5]对应二叉树1 / \ 2 3 / \ 4 5后序遍历过程访问节点左子树深度 left右子树深度 right经过该节点的候选直径 leftright返回给父节点的深度4叶子00015叶子0001211223叶子000112133全局最大值在节点2处先被更新为2随后在根节点1处被更新为3最终答案为3。注意2号节点贡献的直径2虽然被根节点的3覆盖但在其它形态的树上例如右子树为空非根节点处的候选值可能就是最终答案这正是边遍历边更新的原因。复杂度分析时间复杂度O(n)每个节点恰好被访问一次递归体内只有常数次操作空间复杂度O(h)h 为树高取决于递归栈深度。最坏情况链状树为 O(n)平均/最好情况平衡树为 O(log n)。仓库源码实现逐行精讲核心代码位于 leetcode/0543.Diameter-of-Binary-Tree/543. Diameter of Binary Tree.go完整源码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func diameterOfBinaryTree(root *TreeNode) int { result : 0 checkDiameter(root, result) return result } func checkDiameter(root *TreeNode, result *int) int { if root nil { return 0 } left : checkDiameter(root.Left, result) right : checkDiameter(root.Right, result) *result max(*result, leftright) return max(left, right) 1 } func max(a int, b int) int { if a b { return a } return b }逐段解读type TreeNode structures.TreeNode类型别名直接复用仓库structures子包中定义的树节点结构避免每个题解目录重复定义。TreeNode的真实定义位于 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }diameterOfBinaryTree入口函数初始化result : 0调用checkDiameter后返回result。这里有一个容易忽略的细节result用指针传入递归函数因为 Go 语言中闭包或值传递都无法直接修改外层局部变量而指针可以让每一层递归共享同一个全局答案。checkDiameter递归核心递归出口root nil返回0空子树深度为 0后序遍历先递归左子树得left再递归右子树得right此时左右子树的深度信息已齐备更新全局答案*result max(*result, leftright)leftright表示以当前节点为路径拐点时跨过该节点的最长边数返回单侧深度return max(left, right) 1向父节点汇报从当前节点向下延伸的最长路径边数1表示当前节点到父节点之间的那条边。max辅助函数题解目录内自带的两个整数取大函数保持代码零外部依赖未使用math.Max因此也无需处理浮点转换。测试用例验证仓库为本题提供了完整测试位于 leetcode/0543.Diameter-of-Binary-Tree/543. Diameter of Binary Tree_test.go采用表驱动 数组转树的测试风格func Test_Problem543(t *testing.T) { qs : []question543{ { para543{[]int{1, 2, 3, 4, 5}}, ans543{3}, }, { para543{[]int{1, 2}}, ans543{1}, }, { para543{[]int{4, -7, -3, structures.NULL, structures.NULL, -9, -3, 9, -7, -4, structures.NULL, 6, structures.NULL, -6, -6, structures.NULL, structures.NULL, 0, 6, 5, structures.NULL, 9, structures.NULL, structures.NULL, -1, -4, structures.NULL, structures.NULL, structures.NULL, -2}}, ans543{8}, }, } ... for _, q : range qs { ... root : structures.Ints2TreeNode(p.one) fmt.Printf(【output】:%v \n, diameterOfBinaryTree(root)) } }三个测试点覆盖了不同形态[1,2,3,4,5]→3直径经过根节点即题目给出的 Example 1[1,2]→1只有一条边验证最简情形第三个长用例 →8这是一棵直径不经过根节点的复杂树包含structures.NULL空位标记与大量负值节点专门用来验证边遍历边更新全局最大值的正确性——若只计算左子树深度 右子树深度这个用例会得出错误答案。测试基础设施Ints2TreeNode 与 NULL测试中的structures.Ints2TreeNode和structures.NULL都来自 structures/TreeNode.goNULL被定义为var NULL -1 63structures/TreeNode.go即 int 类型的最小值用于在层序数组里标记空节点Ints2TreeNodestructures/TreeNode.go采用**层序遍历BFS**方式把[]int还原成二叉树先以第一个元素建根再用队列逐层挂载左右孩子遇到NULL标记则跳过该孩子。仓库中大量二叉树题解复用这一工具测试数据只需写层序数组无需手工构造指针。本地运行测试在仓库根目录执行以下命令即可验证依赖go 1.19模块定义见 go.mod# 只运行本题测试 go test -v ./leetcode/0543.Diameter-of-Binary-Tree/... # 运行全部 leetcode 题解测试并生成覆盖率 ./gotest.sh仓库的 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性生成合法的覆盖率文件这正是项目 README 中100% test coverage说法的由来coverage.txt位于仓库根目录可直接用 Codecov 等工具解析。边界情况与易错点直径单位是边数leftright本身就是边数子树深度以边计无需再加 1。若误用节点数答案为leftright1全部测试都会失败。路径可以不经过根必须在递归过程中对每个节点执行*result max(*result, leftright)不能只在根节点算一次。result必须用指针传递否则内层递归对result的修改在外层不可见最终返回的永远是0。空树与单节点题目约束节点数 1但函数对空树依然正确返回 0单节点树返回 0没有边这是直径的定义使然。max(left, right) 1的1不能丢它代表当前节点到父节点的那条边丢了会导致父节点拿到的深度少 1。与其他题解的关系本题是二叉树递归模板链条上承上启下的一环前置知识0104.Maximum-Depth-of-Binary-Tree最大深度checkDiameter的返回值部分正是最大深度题的解体同型题目0110.Balanced-Binary-Tree平衡二叉树同样使用后序位置计算左右子树高度并判断的模式0124.Binary-Tree-Maximum-Path-Sum二叉树中的最大路径和则是本题的加权变体——把边数之和换成节点值之和统一模式三者都是递归返回子树单向最优值 闭包/指针维护全局最优值理解本题即可举一反三。仓库内所有题解目录遵循统一组织方式每个题目一个目录内含题目名.go题解、题目名_test.go测试与README.md题面、思路、代码全部复用 structures 子包的基础数据结构方便横向对照阅读。总结直径 任意两节点间最长路径的边数可能不经过根节点解法模板后序遍历中对每个节点用leftright更新全局最大值向上返回max(left,right)1时间复杂度 O(n)、空间复杂度 O(h)与最大深度题同构仓库题解通过*result指针维护全局答案配套 3 组测试用例含直径不经过根节点的复杂用例验证正确性可在 leetcode/0543.Diameter-of-Binary-Tree 目录下直接运行测试复现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考