LeetCode 2020-11-08: Binary Tree Tilt

LeetCode daily challenge の問題 Binary Tree Tilt (easy) の挑戦メモです。

問題の概要

• 与えられた二分木について、以下の計算を再帰的に行い、その結果である tilt の合計を求める
  1. あるノードにおける左部分木と右部分木それぞれのノードが保有する値の合計を求める
  2. 求めた左右それぞれの部分木の合計について差分をとり、その絶対値を tilt とする

考え方

• これは問題にある内容を素直に実装するしか他ないですね…
• ちょっと考えるべき点としては、左右の部分木の値の合計を求めつつ、tilt の合計を求める必要があるので再帰呼び出しするメソッドの戻り値などをどうするか、かな？
  • 部分木の合計と tilt の合計の両方を同時に戻り値として返却できればいいのだけど、Java はそういうのをスマートに効率よく実現できないので…
• 今回はちょっと邪道ではあるけど、インスタンス変数を用意してそこに tilt の合計を保持させることにしてみたよ
• 実装して submit → 一発 accept 💪
  • この程度の問題なら難なく 0ms / beats 100% 達成できますね！

コード

class Solution {
    int result;

    public int findTilt(TreeNode root) {
        result = 0;
        findTiltRecursive(root);
        return result;
    }

    int findTiltRecursive(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = findTiltRecursive(node.left);
        int rightSum = findTiltRecursive(node.right);

        result += Math.abs(leftSum - rightSum);

        return leftSum + rightSum + node.val;
    }
}