对每个节点计算坡度,利用后续遍历,累加求坡度和。
每个节点的坡度,是每个节点的左右子树之和的绝对值。
class Solution{ int count = 0; public int findTilt(TreeNode root) { traverse(root); return count; } int traverse(TreeNode root){ if(root == null){ return 0; } int leftSum = traverse(root.left); int rightSum = traverse(root.right); //后序遍历 count += Math.abs(leftSum - rightSum); //每个节点的坡度,是每个节点的左右子树之和的绝对值 return leftSum + rightSum + root.val; } }