題目

我的想法

從根節點開始，求出每個幾點的度，然后累加。代碼如下：

# 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） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

總結

以上是生活随笔為你收集整理的563. 二叉树的坡度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。