手撸二叉树之二叉树的坡度

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

输入：root = [4,2,9,3,5,null,7]输出：15解释：节点 3 的坡度：|0-0| = 0（没有子节点）节点 5 的坡度：|0-0| = 0（没有子节点）节点 7 的坡度：|0-0| = 0（没有子节点）节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15

输入：root = [21,7,14,1,1,2,2,3,3]输出：9

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    // 坡度    private int tilt = 0;    public int findTilt(TreeNode root) {        traverse(root);        return tilt;    }
    public int traverse(TreeNode root) {        // 终止条件，空树的节点之和为0        if (root == null) {            return 0;        }         // 计算当前节点的左子树节点之和        int left = traverse(root.left);        // 计算当前节点的右子树节点之和        int right = traverse(root.right);        // 计算当前节点的坡度并加入结果        tilt += Math.abs(left - right);        // 返回以当前节点为根的整棵树的节点之和        return left + right + root.val;    }}