二叉树的坡度-LeetCode

563. 二叉树的坡度 - Binary Tree Tilt

🎯 问题描述（来源于LeetCode）

描述：
给定一个二叉树的根节点 root，计算并返回整个树的坡度。
一个节点的坡度定义为：该节点左子树所有节点之和与右子树所有节点之和的差的绝对值。
空节点的坡度为 0。
整棵树的坡度是所有节点坡度之和。

说明：

• 子树和包括该节点及其所有后代节点。
• 坡度不包含节点自身的值，只计算左右子树和的差。

示例：

• 示例 1：

输入: root = [1,2,3]
输出: 1
解释: 节点2的坡度 = |0-0| = 0，节点3的坡度 = |0-0| = 0，节点1的坡度 = |2-3| = 1，总和 = 1。

• 示例 2：

输入: root = [4,2,9,3,5,null,7]
输出: 15
解释: 节点3的坡度=0，节点5的坡度=0，节点7的坡度=0，节点2的坡度=|3-5|=2，节点9的坡度=|0-7|=7，节点4的坡度=|(2+3+5)-(9+7)|=|10-16|=6，总和=2+7+6=15。

💻 解题思路

思路1：后序遍历 + 重复计算子树和

算法步骤

1. 定义辅助函数 getSum(node)：

   • 返回以 node 为根的子树所有节点值之和。
   • 递归终止：如果 node 为 None，返回 0。
   • 否则返回 getSum(node.left) + getSum(node.right) + node.val。

2. 主函数 findTilt(root)：

   • 如果 root 为 None，返回 0。
   • 递归计算左子树的坡度：findTilt(root.left)
   • 递归计算右子树的坡度：findTilt(root.right)
   • 计算当前节点的坡度：abs(getSum(root.left) - getSum(root.right))
   • 返回三者之和。

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        def getSum(node):
            if node is None:
                return 0
            return getSum(node.left) + getSum(node.right) + node.val
        
        if root is None:
            return 0
        return (self.findTilt(root.left) + 
                self.findTilt(root.right) + 
                abs(getSum(root.left) - getSum(root.right)))

思路1：📊 性能分析

• 时间复杂度：$O(n^2)$，每个节点调用 getSum 遍历其所有子孙节点，存在大量重复计算。
• 空间复杂度：$O(n)$，递归栈深度为树高。

---

思路2：后序遍历 + 同时返回子树和与累计坡度（优化）

算法步骤

1. 定义递归函数 dfs(node)：

   • 返回值：元组 (子树和, 以该节点为根的累计坡度)。
   • 递归终止：如果 node 为 None，返回 (0, 0)。

2. 递归计算左右子树：

   • 得到 (left_sum, left_tilt) = dfs(node.left)
   • 得到 (right_sum, right_tilt) = dfs(node.right)

3. 计算当前节点信息：

   • 当前子树和：cur_sum = left_sum + right_sum + node.val
   • 当前节点坡度：cur_tilt = abs(left_sum - right_sum)
   • 累计总坡度：total_tilt = left_tilt + right_tilt + cur_tilt

4. 返回元组 (cur_sum, total_tilt)。

5. 主函数：调用 dfs(root)，返回结果元组的第二个元素（总坡度）。

思路2：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return (0, 0)  # (子树和, 累计坡度)
            left_sum, left_tilt = dfs(node.left)
            right_sum, right_tilt = dfs(node.right)
            cur_sum = left_sum + right_sum + node.val
            cur_tilt = abs(left_sum - right_sum)
            total_tilt = left_tilt + right_tilt + cur_tilt
            return (cur_sum, total_tilt)
        return dfs(root)[1]

思路2：📊 性能分析

• 时间复杂度：$O(n)$，每个节点只被访问一次，所有计算为 $O(1)$。
• 空间复杂度：$O(n)$，递归栈深度为树高（最坏情况 $O(n)$）。

思考

• 思路1 直观但效率低，思路2 通过后序遍历将子树和与坡度同时向上传递，避免了重复计算，是本题的最优解。
• 这种“一次递归返回多个值”的技巧在树形 DP 中非常常见，例如求二叉树的最大路径和、二叉树的直径等问题。
• 也可以使用迭代后序遍历（栈 + 状态标记）实现，但递归代码更简洁易读。