楔子
大家好，我是张桃狮
电梯游戏的定义是，可以让我在电梯里面玩一局的游戏，不用联网，10-20秒就可以爽到。
最近我在电梯里经常玩的游戏是手机扫雷Antimine。
没错就是那个Windows电脑自带的游戏扫雷，不过现在的Win10、Win11好像已经不带这个游戏了。
下载网址如下。
https://github.com/lucasnlm/antimine-android
注意右边的Releases里面只有源码，没有apk安装文件。
我是从Readme里的Get it on F-Droid下载的。
Antimine是一款类似扫雷的益智游戏。目标是标记布满地雷的格子，使地雷更安全，同时不引爆任何地雷。
当你标记了雷区内的所有地雷时，你就赢得了游戏。小心别触发它！
这游戏有个特点，第一次点击绝对不会踩到地雷。
Antimine默认开启了无猜测算法，理论上所有地雷都可以通过逻辑判断扫出来。
但是我的水平还是会遇到需要碰运气的局面，建议先使用游戏自带的提示功能，实在搞不定在蒙一把。
频繁点击未点开区域附近的地雷数字，可以让电脑辅助判断地雷和非地雷区域，相当于电脑上在数字格子上同时按鼠标左键和右键（按鼠标中键也可以）。
这种方法可以让扫雷瞬间变得电竞起来，是的，扫雷其实拼的是手速APM。
当然，也会遇到辅助判断扫不开的区域，这个时候需要手动判断地雷和非地雷的位置。
我在电梯里玩的是9x9的新手模式，一共有10颗地雷。
运气好的时候9秒就可以扫完一局，但是经常会因为点错格子导致半途而废。
游戏上方可以看到地图上还剩多少颗地雷，理论上可以用穷举法把一些难以解开的局面扫开。
我尝试将一些比较难判断的局面截图发给豆包和Deepseek，你猜怎么着，他两都搞不定。
AI大模型都搞不定的游戏，我玩的更起劲了。
感兴趣的不妨亲自挑战一下，Antimine的背景音乐还挺好听的。
闲话讲完，咱们继续力扣刷题学编程。
力扣563. 二叉树的坡度
给你一个二叉树的根节点 root ，计算并返回 整个树的坡度 。
一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。
示例 1：
输入：root = [1,2,3]输出：1解释：节点 2 的坡度：|0-0| = 0（没有子节点）节点 3 的坡度：|0-0| = 0（没有子节点）节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）坡度总和：0 + 0 + 1 = 1
示例 2：
输入：root = [4,2,9,3,5,null,7]输出：15解释：节点 3 的坡度：|0-0| = 0（没有子节点）节点 5 的坡度：|0-0| = 0（没有子节点）节点 7 的坡度：|0-0| = 0（没有子节点）节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15
示例 3：
输入：root = [21,7,14,1,1,2,2,3,3]输出：9
提示：
- •
-1000 <= Node.val <= 1000
我的思路
我想写三个函数来做这道题。
第一个函数负责中序遍历并返回子树所有节点值的列表，其实这里用前序、中序、后序都行。
第二个函数调用第一个函数求左右子树的节点值之和，再取差的绝对值。
第三个函数再中序遍历整棵树，对每个节点调用第二个函数计算坡度并返回列表。
最后将第三个函数返回的结果累加
from typing import Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def findTilt(self, root: Optional[TreeNode]) -> int: # 第一个函数：中序遍历，返回以 node 为根的子树所有节点值的列表 def inorder(node): if not node: return [] return inorder(node.left) + [node.val] + inorder(node.right) # 第二个函数：计算某个节点的坡度 def get_tilt(node): if not node: return 0 left_sum = sum(inorder(node.left)) # 左子树节点值之和 right_sum = sum(inorder(node.right)) # 右子树节点值之和 return abs(left_sum - right_sum) # 第三个函数：中序遍历整棵树，对每个节点计算坡度并返回列表 def traverse(node): if not node: return [] return traverse(node.left) + [get_tilt(node)] + traverse(node.right) return sum(traverse(root))
力扣提交通过，时间复杂度，空间复杂度O(n)。
个人认为这个代码时间复杂度爆炸，没想到力扣提交没有超时。
老夫代码的复杂度起步，计算机硬件性能提升的速度，已经追不上我代码的复杂度🐶
可以看出第一个函数和第三个函数的结构是一样的，要是能把它们跟第二个函数合并在一起，组成一个函数就好了。
可惜我能力有限，调试半天还是失败了。
最后无奈采用这种分块的方法，复杂度是高了点，好歹不会出错。
力扣官方题解
方法一：深度优先搜索
class Solution: def __init__(self): self.ans = 0 def findTilt(self, root: TreeNode) -> int: self.dfs(root) return self.ans def dfs(self, node): if not node: return 0 sum_left = self.dfs(node.left) sum_right = self.dfs(node.right) self.ans += abs(sum_left - sum_right) return sum_left + sum_right + node.val
力扣提交通过，时间复杂度O(n)，空间复杂度O(n)。
米娜桑，鼓掌吧，这可是我想破脑子都想不出的代码。
力扣网友Benhao的代码
class Solution: def findTilt(self, root: TreeNode) -> int: def dfs(node): if not node: return 0, 0 l_sum, l_diff = dfs(node.left) r_sum, r_diff = dfs(node.right) return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum) return dfs(root)[1]
力扣提交通过，时间复杂度O(n)，空间复杂度O(n)。
好家伙，这个元组返回法，我用最简单的二叉树从头推了一遍才勉强看懂。
1 / \ 2 3
调用 dfs(1)：
- •
dfs(2) 调 dfs(None) → 返回 (0,0) - •
dfs(2) 调 dfs(None) → 返回 (0,0) - • 返回
(0+0+2, 0+0+abs(0-0)) = (2, 0)
- •
dfs(3) 调 dfs(None) → (0,0) - •
dfs(3) 调 dfs(None) → (0,0) - • 返回
(0+0+3, 0+0+abs(0-0)) = (3, 0)
- • 返回
(2+3+1, 0+0+abs(3-2)) = (6, 1)
最后 findTilt 返回 dfs(1)[1] = 1。
我是个编程爱好者，小白级别的，如果你跟我一样希望通过力扣刷题，学习各种奇妙的算法，可以关注我，大家一起学习。
