563. 二叉树的坡度

题目

我的想法

从根节点开始，求出每个几点的度，然后累加。代码如下：

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def node_Tilt(root):# 每个节点的坡度if not root:return 0if not (root.left or root.right):# 是叶子节点return 0else:return abs(sum_of_sub_tree(root.left) - sum_of_sub_tree(root.right))def sum_of_sub_tree(root):'''求当前子树为根节点的和:param root::return:'''if not root:return 0stack = []sum_node = 0#last_visit = rootwhile stack or root:while root:# print(root.val)# 先序sum_node += root.valstack.append(root)root = root.leftroot = stack.pop()if root.right:# print(root.val)# 中序root = root.rightelse:root = Nonereturn sum_nodeclass Solution:def findTilt(self, root: TreeNode) -> int:if not root:return 0# a = node_Tilt(root)# print('***', root.val, a)# l = self.findTilt(root.left)# r = self.findTilt(root.right)# return a + l + rreturn node_Tilt(root)+self.findTilt(root.left)+self.findTilt(root.right)

有个问题：
是从根节点向下遍历的，根节点一下的节点遍历了多次。造成了时间的浪费。

参考:基于后续遍历的思想求解二叉树的坡度

class Solution:def findTilt(self, root: TreeNode) -> int:def search(root: TreeNode) -> (int, int): # 返回节点和，累积坡度if not root:return 0, 0else:sl, pl = search(root.left) # 递归求解子问题sr, pr =search(root.right) # 递归求解子问题 return sr + sl + root.val, abs(sl - sr) + pl + pr # 跟节点的节点和，累积坡度与子问题的递归关系（合并子问题，形成原问题的解）_, p = search(root)return p作者：lzx1997
链接：https://leetcode-cn.com/problems/binary-tree-tilt/solution/ji-yu-hou-xu-bian-li-de-si-xiang-qiu-jie-d982/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！