二叉树的坡度

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

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

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

示例：

输入：root = [1,2,3]
输出：1
解释：
节点 2 的坡度：|0-0| = 0（没有子节点）
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
坡度总和：0 + 0 + 1 = 1
  

思路

解法一：

使用递归法求解每次写递归，都按照这三要素来写

确定递归函数的输入和输出： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

本题为例：

输入根节点，输出节点总和与左右节点的差值。
确定终止条件，root节点为空
递归遍历左子树和右子树，将结果相加

class Solution:
    """递归法"""
    def findTilt(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:
                return 0,0
            l_sum, l_diff = dfs(root.left)
            r_sum, r_diff = dfs(root.right)
            return l_sum + r_sum + root.val, l_diff + r_diff + abs(r_sum - l_sum)
        return dfs(root)[1]
  