C++で二分木のユニバリュー（単一値）部分木を数える方法

問題の概要

二分木が与えられたとき、その中に含まれる「ユニバリュー（単一値）部分木」の数を数えることを考えます。ここでいうユニバリュー部分木とは、その部分木を構成するすべてのノードが同じ値を持つような部分木のことです。

例えば、入力が root = [5,1,5,5,5,null,5] の場合を考えてみましょう。

このとき出力は 4 になります。これは、値 5 を持つ葉ノードが2つ、右側の値 5 を根とする部分木（親子ともに 5）が1つ、さらにその先の葉ノードが1つ存在し、合計 4 つのユニバリュー部分木が見つかるためです。

解法のアプローチ

この問題は、木を再帰的にたどりながら「そのノードを根とする部分木がユニバリューであるか」をボトムアップで判定することで解けます。具体的な手順は以下のとおりです。

• solve() 関数を定義します。この関数はノードを引数として受け取ります。
• ノードが空（NULL）の場合は true を返します。
• left := solve(ノードの左の子)、right := solve(ノードの右の子) を再帰的に呼び出します。
• left または right のどちらかが false の場合は false を返します。
• ノードの左の子が存在し、かつその値がノード自身の値と異なる場合は false を返します。
• ノードの右の子が存在し、かつその値がノード自身の値と異なる場合も false を返します。
• ここまでのチェックをすべて通過できれば、その部分木はユニバリューなので ret を 1 増やし、true を返します。

メインの処理では、次の手順を実行します。

• カウンタ ret を 0 で初期化します。
• solve(root) を呼び出して木全体を走査します。
• 最後に ret を結果として返します。

計算量について

各ノードを一度だけ訪問するため、時間計算量は O(n) です。再帰呼び出しに伴うスタックの深さは木の高さに依存し、偏った木の場合は最悪で O(n) となります。

C++での実装例

以下の実装を見ると、アルゴリズムの動きがより理解しやすくなるでしょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   int ret;
   bool solve(TreeNode* node){
      if (!node || node->val == 0)
         return true;
      bool left = solve(node->left);
      bool right = solve(node->right);
      if (!left || !right)
         return false;
      if (node->left && node->left->val != 0 && node->val != node->left->val)
         return false;
      if (node->right && node->right->val != 0 && node->val != node->right->val)
         return false;
      ret++;
      return true;
   }
   int countUnivalSubtrees(TreeNode* root){
      ret = 0;
      solve(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,1,5,5,5,NULL,5};
   TreeNode *root = make_tree(v);
   cout << (ob.countUnivalSubtrees(root));
}

入力

{5,1,5,5,5,NULL,5}

出力

4