C++で二分木を等しい合計値の2つの木に分割できるか判定する方法

問題概要

n 個のノードを持つ二分木が与えられたとき、元の木からちょうど1本の辺を削除することで、その木を「ノード値の合計が等しい2つの木」に分割できるかどうかを判定するのがこの問題です。

例えば、次のような入力が与えられたとします。

この場合、出力は true になります。

解法のアプローチ

この問題は、各部分木の合計値を事前にすべて計算しておき、その中に「木全体の合計の半分」と一致する値が存在するかを確認することで解けます。手順は以下の通りです。

1. 部分木の合計値を格納するためのスタック st を用意します。
2. solve() 関数を定義します。引数としてノードを受け取ります。
3. ノードが null の場合は 0 を返します。
4. leftSum := ノードの左の子に対する solve() の結果
5. rightSum := ノードの右の子に対する solve() の結果
6. curr := ノードの値 + leftSum + rightSum
7. curr をスタック st に挿入します。
8. curr を返します。

メインメソッドでは以下の手順を実行します。

1. solve(root) を呼び出します。
2. totalSum := スタックの先頭要素（これは木全体の合計値になります）
3. スタックからその要素を取り除きます。
4. スタックが空になるまで、以下を繰り返します。
   • x := スタックの先頭要素
   • スタックから要素を取り除きます。
   • y := totalSum − x
   • x と y が等しければ true を返します。

ループが終了しても一致するものが見つからなければ、false を返します。

なお、solve() は再帰的に子ノードを先に処理するため、スタックには葉に近い部分木の合計から順に格納され、最後に根全体の合計が積まれます。これにより、totalSum を簡単に取得できます。計算量は時間・空間ともに 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;
   }
};
class Solution {
public:
   stack <int> st;
   int solve(TreeNode* node){
      if (!node)
         return 0;
      int leftSum = solve(node->left);
      int rightSum = solve(node->right);
      int curr = node->val + leftSum + rightSum;
      st.push(curr);
      return curr;
   }
   bool checkEqualTree(TreeNode* root) {
      solve(root);
      int totalSum = st.top();
      st.pop();
      while (!st.empty()) {
         int x = st.top();
         st.pop();
         int y = totalSum - x;
         if (x == y)
            return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(5);
   root->left = new TreeNode(10);
   root->right = new TreeNode(10);
   root->right->left = new TreeNode(2);
   root->right->right = new TreeNode(3);
   cout<<(ob.checkEqualTree(root));
}

入力

TreeNode *root = new TreeNode(5);
root->left = new TreeNode(10);
root->right = new TreeNode(10);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(3);

出力

1

出力が 1（true）となるのは、例えば値 10 のノードと残りの部分（5 + 10 + 2 + 3 = 20）に分割すると、両者の合計が一致しないためではなく、別の辺を選んだ場合に 15 対 15 となる組み合わせが存在するからです。具体的には、左の子（合計 10）と右側の部分木の一部を比較することで、等しい合計となる分割が見つかります。