企业官网建设流程全解析

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）。

定义分两层，需要严格区分：

1. 节点坡度（node tilt）：某个节点的坡度 = |左子树所有节点值之和 − 右子树所有节点值之和|。
2. 整树坡度（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}一致）。

记住：坡度统计的是整棵子树的"总和"，而不是单个节点。这一点想清楚，题目就变成了纯粹的树遍历问题。

三、解法思路：一次后序遍历搞定两个任务

整棵树的坡度需要用到每个节点的"子树节点值总和"，而子树总和只有在先遍历完左右子树之后才能确定。因此后序遍历（先左、再右、最后处理根）是天然匹配的遍历顺序。

后序遍历可以同时完成两件事：

1. 递归返回当前子树所有节点值的总和（供父节点计算坡度使用）；
2. 在递归回溯的过程中，把每个节点的坡度累加到全局结果变量上。

时间复杂度为 O(n)，每个节点恰好访问一次；空间复杂度为 O(h)，h 为树高（递归调用栈深度）。

四、仓库源码解析：findTilt 与 findTiltDFS

LeetCode-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 递归函数 findTiltDFS

findTiltDFS的返回值是"以 root 为根的子树所有节点值之和"，内部逻辑分四步：

1. 空节点返回 0：空子树和为空，坡度累加量为 0，正好符合题目"空节点的坡度为 0"的约定；
2. 递归左子树：left := findTiltDFS(root.Left, sum)，得到左子树总和；
3. 递归右子树：right := findTiltDFS(root.Right, sum)，得到右子树总和；
4. 累计坡度并向上返回：
   • *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 组用例：

其中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-Go（Go 1.19），并通过replace指令将structures等子包映射到本地目录。可以直接运行该题测试：

go test -v ./leetcode/0563.Binary-Tree-Tilt/

若想验证整个仓库的题解与覆盖率，可执行仓库根目录的 gotest.sh 脚本，它会一次性对所有leetcode/...包做原子模式覆盖率统计并生成coverage.txt：

bash 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