【LeetCode】二叉树的坡度 Java 题解

2021 年 11 月 18 日
本文字数：1316 字
阅读完需：约 4 分钟

题目描述

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

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

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

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-tilt著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是二叉树题目，题干较长，题目要求求出节点的坡度之和。节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值。
根据题目描述，我们需要遍历整个二叉树的每一个节点。常用的遍历算法是 DFS 和 BFS。结合这个题目，DFS 更加适合。
DFS 递归的终止条件是 node == null, 分别求出左右子树节点之和，然后相减，即为当前节点坡度。同时，使用 leftSum + rightSum + node.val，即可快速求出 node 作为根结点的树的结点之和。这里很巧妙。具体实现代码如下：

通过代码

/** * 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 {        int ans = 0;
    public int findTilt(TreeNode root) {        if (root == null) {            return ans;        }
        dfs(root);
        return ans;    }
    public int dfs(TreeNode node) {        if (node == null) {            return 0;        }                int leftSum = dfs(node.left);        int rightSum = dfs(node.right);
        ans += Math.abs(leftSum - rightSum);
        return leftSum + rightSum + node.val;    }}