Note

サンタ・クララ在住エンジニアの勉強・生活の記録です

Leetcode 894 All Possible Full Binary Trees

Leetcode 894のAll Possible Full Binary Treesです。

与えられたノードの数Nで構成される全二分木をすべて返しなさいという問題です。全二分木は、子ノードも全二分木であるという性質を利用します。これを実装するallPossibleFBTはこんな処理になります。

  • N == 1, 1つのノードを返す
  • N % 2 == 0, 空配列を返す
  • それ以外:
    • 左のノードに入る数を1, 3, 5, .. Nまで回し、それぞれの数iに対しallPossibleFBT(i)を呼ぶ。ここで返ってくるのが、左のノードになりうるすべての全二分木である。それぞれのiに対し、allPossibleFBT(N - i - 1)を呼ぶ。1を引く理由は根っこのルートを引くためです。
    • 左のノードになりうるすべてのノードに対し、右のノードになりうるすべてのノードをマッチし、新しい二分木を作る。これがN個のノードで構成される全二分木の一つです。できた二分木を答えのListに追加する。

実装:

public static List<TreeNode> allPossibleFBT(int N) {
    List<TreeNode> answer = new ArrayList<TreeNode>();
    if (N % 2 == 0) {
        return answer;
    }
    if (N == 1) {
        answer.add(new TreeNode(0));
        return answer;
    }
    for (int i = 1; i < N; i += 2) {
        List<TreeNode> L = allPossibleFBT(i);
        List<TreeNode> R = allPossibleFBT(N - i - 1); // -1 for the root
        
        for (int j = 0; j < L.size(); j++) {
            TreeNode l = L.get(j);
            for (int k = 0; k < R.size(); k++) {
                TreeNode r = R.get(k);
                
                TreeNode root = new TreeNode(0);
                root.left = l;
                root.right = r;
                answer.add(root);
            }
        }
    }
    
    return answer;
}

解説では、これをメモ化してますが、1 <= N <= 20なのでメモ化しなくても十分通ります。

解けなかった理由は

  • 子ノードも全二分木であることを思いつかなかった/知らなかった
  • 自分自身を2回呼び、返ってきたものを使い、答えを出す使い方をしたことがなかった

です。ノードを渡す再帰の実装ばかり考えていました。