二叉树的坡度

标签: 树 深度优先搜索 二叉树

难度: Easy

给你一个二叉树的根节点 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

提示：

  • 树中节点数目的范围在 [0, 104] 内
  • -1000 <= Node.val <= 1000

Submission

运行时间: 18 ms

内存: 17.2 MB

# 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:
        self.ans = 0
        def sumTree(node: TreeNode):
            if not node:
                return 0
            L = sumTree(node.left)
            R = sumTree(node.right)
            self.ans += abs(L-R)
            return node.val+L+R
        sumTree(root)
        return self.ans

Explain

题解采用递归方法遍历二叉树的每个节点，并计算每个节点的坡度。函数sumTree是一个递归函数，它计算并返回当前节点及其所有子节点的值之和。在计算过程中，该函数还计算当前节点左右子树的值之和的差的绝对值，并累加到全局变量self.ans中，以计算整棵树的坡度总和。递归的基础情况是当遇到空节点时，返回0，表示该节点的值之和为0。

时间复杂度: O(n)

空间复杂度: O(h)，其中h是树的高度

# 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:
        self.ans = 0  # 初始化总坡度为0
        def sumTree(node: TreeNode) -> int:
            if not node:
                return 0  # 空节点的和为0
            L = sumTree(node.left)  # 计算左子树的节点之和
            R = sumTree(node.right)  # 计算右子树的节点之和
            self.ans += abs(L - R)  # 计算当前节点的坡度，并累加到总坡度
            return node.val + L + R  # 返回当前节点及其子树的节点之和
        sumTree(root)  # 从根节点开始计算
        return self.ans  # 返回总坡度

Explore

在递归函数sumTree中，每次调用都会处理一个特定的节点，并在该节点上直接计算其坡度。这是通过获取其左右子树的总和，计算这两个数之差的绝对值来实现的。每个节点在递归过程中只被访问一次，因此每个节点的坡度也只被计算一次。这确保了整个树中的每个节点的坡度都准确地被计算了一次，不会重复计算。

递归函数sumTree返回当前节点及其所有子节点的值的总和。这个返回值通过两个子递归调用（对左子树和右子树）得到，并加上当前节点的值。这个总和不仅用于上层递归调用中父节点的总和计算，更重要的是，使用左右子树的总和（分别为L和R）来计算当前节点的坡度，即`abs(L - R)`。这样，每个节点的坡度都是基于其子树的正确总和计算出来的，从而确保了整棵树的坡度计算的准确性。

在递归函数sumTree中，处理空节点的情况是通过检查当前节点是否为null来实现的。如果是空节点（null），函数直接返回0。这种设计确保当递归到达树的底部且没有更多的子节点时，不会尝试访问null节点的属性，从而避免了null引用错误。这也使得空节点对于父节点的坡度计算不会有贡献，因为它们的值总和为0。