LeetCode-Go 题解 | 563. Binary Tree Tilt后序遍历求解二叉树坡度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 563 题「Binary Tree Tilt二叉树的坡度」展开结合开源仓库 LeetCode-Go 中该题目的 Go 实现与测试代码讲解坡度的准确定义、易错点辨析以及如何用一次后序遍历同时完成子树求和与坡度累计。读完本文你将掌握这类子树求和 全局累计双返回值递归模式的 Go 写法并能直接复用仓库中的测试框架验证自己的解法。一、题目定义什么是坡度题目要求给定一棵二叉树返回整棵树的坡度tilt of the whole tree。定义分两层需要严格区分节点坡度node tilt某个节点的坡度 |左子树所有节点值之和 − 右子树所有节点值之和|。整树坡度whole tree tilt所有节点坡度的累加和。补充约定空节点null node的坡度为 0任何子树的节点值之和不会超过 32 位整数范围所有坡度值也不会超过 32 位整数范围。官方示例输入 1 / \ 2 3 输出1推算过程节点 2无左右子树左子树和为 0右子树和为 0坡度 |0 − 0| 0节点 3同理坡度 0节点 1左子树和为 2右子树和为 3坡度 |2 − 3| 1整树坡度 0 0 1 1。二、核心易错点坡度 ≠ 左右孩子值之差原题文档特别强调这一题虽然是简单题但如果对坡度理解不对很容易写错。常见的错误理解是节点的坡度 |该节点左孩子值 − 右孩子值|。这是只针对直接左右孩子的差值而题目要求的坡度计算的是左子树所有节点值的总和与右子树所有节点值的总和的差值。看一个能区分这两种理解的例子该例来自本仓库的测试用例1 / \ 2 3 / \ 4 5若按左右孩子值之差理解节点 1 的坡度 |2 − 3| 1会得到错误结果按正确定义节点 1 的左子树和为 2 4 6右子树和为 3 5 8坡度 |6 − 8| 2节点 2 的坡度 |4 − 0| 4节点 3 的坡度 |0 − 5| 5节点 4、5 的坡度均为 0。整树坡度 2 4 5 11与测试用例ans563{11}一致。记住坡度统计的是整棵子树的总和而不是单个节点。这一点想清楚题目就变成了纯粹的树遍历问题。三、解法思路一次后序遍历搞定两个任务整棵树的坡度需要用到每个节点的子树节点值总和而子树总和只有在先遍历完左右子树之后才能确定。因此后序遍历先左、再右、最后处理根是天然匹配的遍历顺序。后序遍历可以同时完成两件事递归返回当前子树所有节点值的总和供父节点计算坡度使用在递归回溯的过程中把每个节点的坡度累加到全局结果变量上。时间复杂度为 O(n)每个节点恰好访问一次空间复杂度为 O(h)h 为树高递归调用栈深度。四、仓库源码解析findTilt 与 findTiltDFSLeetCode-Go 仓库中该题的实现位于 leetcode/0563.Binary-Tree-Tilt/563. Binary Tree Tilt.go完整代码如下package leetcode import ( math github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode func findTilt(root *TreeNode) int { if root nil { return 0 } sum : 0 findTiltDFS(root, sum) return sum } func findTiltDFS(root *TreeNode, sum *int) int { if root nil { return 0 } left : findTiltDFS(root.Left, sum) right : findTiltDFS(root.Right, sum) *sum int(math.Abs(float64(left) - float64(right))) return root.Val left right }4.1 入口函数 findTilt空树直接返回 0声明局部变量sum作为坡度累加器调用findTiltDFS(root, sum)触发遍历最终返回sum即整树坡度。这里sum以指针形式传入递归函数是因为 Go 语言中基本类型按值传递而递归过程中每个栈帧都需要向这个累加器写入坡度必须通过指针共享同一份内存才能正确累计。4.2 递归函数 findTiltDFSfindTiltDFS的返回值是以 root 为根的子树所有节点值之和内部逻辑分四步空节点返回 0空子树和为空坡度累加量为 0正好符合题目空节点的坡度为 0的约定递归左子树left : findTiltDFS(root.Left, sum)得到左子树总和递归右子树right : findTiltDFS(root.Right, sum)得到右子树总和累计坡度并向上返回*sum int(math.Abs(float64(left) - float64(right)))当前节点的坡度 |左子树和 − 右子树和|累加进全局结果return root.Val left right把当前节点的值与左右子树总和相加作为本子树的总和返回给上一层。注意第 4 步中用math.Abs(float64(...))计算绝对值后再转回int这是 Go 标准库对int绝对值计算的标准写法Go 的math包只提供浮点版本的Abs。4.3 TreeNode 类型来源代码通过别名type TreeNode structures.TreeNode复用了仓库通用数据结构包 structures/TreeNode.go 中定义的标准二叉树节点type TreeNode struct { Val int Left *TreeNode Right *TreeNode }该文件还提供了Ints2TreeNode将层序[]int转成树、Tree2ints、PreIn2Tree、InPost2Tree等一系列工具函数全仓库的二叉树题目都共用这套结构这也是 LeetCode-Go 保持题解代码精简的关键设计。五、测试用例验证该题对应的测试文件是 leetcode/0563.Binary-Tree-Tilt/563. Binary Tree Tilt_test.go采用表驱动测试table-driven test模式共覆盖 5 组用例输入层序数组对应树结构期望输出[]空树0[1]单节点0[3,9,20,NULL,NULL,15,7]满二叉树3 的左子树为 9右子树为 20(15,7)41[1,2,3,4,NULL,NULL,5]非满二叉树见第二节示例11[1,2,3,4,NULL,5]左右子树高度不对称的树11其中structures.NULL是在 structures/TreeNode.go 中定义的哨兵值var NULL -1 63用于在层序数组中标记空节点。测试中的关键调用链root : structures.Ints2TreeNode(p.one) // 层序数组 → 二叉树 fmt.Printf(【output】:%v \n, findTilt(root)) // 计算整树坡度以用例[3,9,20,NULL,NULL,15,7]为例手动演算验证输出 41节点 15、7坡度 0子树和分别为 15、7节点 20坡度 |15 − 7| 8子树和 20 15 7 42节点 9坡度 0子树和 9节点 3坡度 |9 − 42| 33子树和 3 9 42 54整树坡度 0 0 8 0 33 41✓运行测试仓库根目录 go.mod 声明了模块github.com/halfrost/LeetCode-GoGo 1.19并通过replace指令将structures等子包映射到本地目录。可以直接运行该题测试go test -v ./leetcode/0563.Binary-Tree-Tilt/若想验证整个仓库的题解与覆盖率可执行仓库根目录的 gotest.sh 脚本它会一次性对所有leetcode/...包做原子模式覆盖率统计并生成coverage.txtbash gotest.sh六、复杂度分析与延伸思考6.1 复杂度时间复杂度 O(n)每个节点在findTiltDFS中恰好被访问一次每个节点上只做常数次算术运算空间复杂度 O(h)递归栈深度取决于树高 h。最坏情况链状树为 O(n)平衡树为 O(log n)。由于题目保证子树和与坡度均在 32 位整数范围内sum与返回值无需担心溢出问题。6.2 延伸同模式题目的通用性后序遍历返回子树汇总信息 外部累加全局结果是二叉树递归题中的经典范式与仓库中 543. Diameter of Binary Tree直径、124. Binary Tree Maximum Path Sum最大路径和、968. Binary Tree Cameras监控二叉树等题目同构。区别仅在于递归函数返回的信息类型总和、深度、节点数等与全局累加的逻辑不同。掌握了 563 题的写法即可触类旁通这一类树形 DP / 后序汇总问题。总结LeetCode 563「Binary Tree Tilt」的核心不在于遍历本身而在于准确理解坡度基于整棵左右子树的节点值总和而非左右孩子值之差。LeetCode-Go 仓库通过一次后序遍历同时完成子树求和与坡度累计两个任务代码简洁且配合表驱动测试覆盖了空树、单节点、满二叉树与不对称树等多种形态是该题目的可靠参考实现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考