leetcode-563. 二叉树的坡度

本文主要是介绍leetcode-563. 二叉树的坡度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个二叉树，计算整个树的坡度。

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

示例:

输入: 1/   \2     3
输出: 1
解释: 
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1

注意:

任何子树的结点的和不会超过32位整数的范围。
坡度的值不会超过32位整数的范围。

解题思路

后序遍历，树形dp，每个结点保存左子树结点之和、右子树结点之和、本结点tilt

成绩

时间>48.18%
空间>6.35%

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def findTilt(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0node_info = {}stack = [(0, root)]while stack:stat, p = stack.pop()if stat == 0:stack.append((1, p))if p.left:stack.append((0, p.left))if p.right:stack.append((0, p.right))else:if p.left and p.right:left_sum = sum(node_info[p.left][:2]) + p.left.valright_sum = sum(node_info[p.right][:2]) + p.right.valtilt = abs(left_sum - right_sum)node_info[p] = [left_sum, right_sum, tilt]elif p.left:left_sum = sum(node_info[p.left][:2]) + p.left.valright_sum = 0tilt = abs(left_sum - right_sum)node_info[p] = [left_sum, right_sum, tilt]elif p.right:left_sum = 0right_sum = sum(node_info[p.right][:2]) + p.right.valtilt = abs(left_sum - right_sum)node_info[p] = [left_sum, right_sum, tilt]else:node_info[p] = [0, 0, 0]tree_tilt = 0for node, val_list in node_info.items():tree_tilt += val_list[2]return tree_tilt