563. 二叉树的坡度--Python

563. 二叉树的坡度--Python

给定一个二叉树，计算整个树的坡度 。
一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树的坡度就是其所有节点的坡度之和。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


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_right - sum_left)
    return sum_left + sum_right + node.val

时间复杂度：O(N)，遍历所有节点
空间复杂度：O(N)，在只有左节点的情况下，要存储n-1个节点值

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-tilt
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。