LeetCode563-二叉树的坡度

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-tree-tilt/

中文链接：https://leetcode-cn.com/problems/binary-tree-tilt/

题目详述

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

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: 
         1
       /   \
      2     3
输出: 1
解释: 
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1

注意:

  1. 任何子树的结点的和不会超过32位整数的范围。
  2. 坡度的值不会超过32位整数的范围。

题目详解

LeetCode543-二叉树的直径 是计算二叉树的直径，本题是计算二叉树的坡度，可能还有其他自定义的属性。事实上，它们的解题思路是一致的，都是定义一个方法辅助计算，然后可以比较容易得到可能的结果，并不断更新。值得注意的是，此类问题往往方法返回值不是我们想要的结果，但这个值可以非常方便地得到结果。对于此类问题，找到恰当的计算方式，就可以很容易解答。

  • 定义一个计算子树中所有结点和的方法。
  • 对于一个结点来说，计算它的左子树和右子树的结点和，它们的差的绝对值就是当前结点的坡度，用这个值更新结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00563 {

    public int findTilt(TreeNode root) {
        int[] res = new int[1];
        dfs(root, res);
        return res[0];
    }

    private int dfs(TreeNode root, int[] res) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left, res);
        int right = dfs(root.right, res);
        res[0] += Math.abs(left - right);
        return root.val + left + right;
    }
}