前言
持续更新了
正文
问题来源
本问题来自leetcode上的563题。
问题描述
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例 1:
输入：
1
/ \
2 3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
分析：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTilt(root *TreeNode) int {
res := 0
dfs(root, &res)
return res
}
func dfs(root *TreeNode, res *int) int {
if root == nil {
return 0
}
l := dfs(root.Left, res)
r := dfs(root.Right, res)
*res += int(math.Abs(float64(l-r)))
return l+r+root.Val
}
总结：
勤思考。
结语
不管怎么样好好加油。
