LeetCode 2020-11-23: House Robber III

House Robber III (medium) の挑戦メモです。

問題の概要

• 与えられた二分木をグラフとしてみたときに、隣接するノードを選ばないようにしつつ、選択したノードが保持する値の合計を最大化する

考え方

• ぱっと見で難しそう〜 😫 って思ったけど、二分木であることを利用すればそんなに難しい問題ではなかった ☺️
• 基本的には深さ優先の再帰処理となる
  • あるノードに着目しているとして、そのノードを「選択した場合」と「選択しなかった場合」について、子ノードを含めた値の合計の最大値をそれぞれ求めてあげる
  • そのノードを「選択した場合」は、左右の 子ノードを選択しなかった場合 のそれぞれの最大値と自身のノードの値を足してその答えとする
  • そのノードを「選択しなかった場合」は、左右の子ノードそれぞれについて、選択した場合としなかった場合の値の大きい方を採用し、その合計を答えとする
• 再帰処理では戻り値を一つしか返せないけど、long の戻り値にして上位・下位 32 ビットそれぞれにノードを選択した場合・しなかった場合の値を入れておけば JVM 的にエコですね 🤗
• そういうわけで実装 → submit → runtime 0ms 達成 🎉

コード

class Solution {
    public int rob(TreeNode root) {
        long result = findMaxRecursive(root);
        return (int) Math.max(result >>> 32, result & 0xffff_ffffL);
    }

    // 戻り値の下位 32 ビットが、そのノードを「選択した場合」の最大値となり、
    // 上位 32 ビットがそのノードを「選択しなかった場合」の最大値となる
    long findMaxRecursive(TreeNode node) {
        if (node == null) {
            return 0;
        }

        long left = findMaxRecursive(node.left);
        long right = findMaxRecursive(node.right);

        return (node.val + (left >>> 32) + (right >>> 32))
                | ((Math.max(left >>> 32, left & 0xffff_ffffL) + Math.max(right >>> 32, right & 0xffff_ffffL)) << 32);
    }
}