C++で最も深いノードをすべて含む最小の部分木を求める方法

問題の概要

ルートを頂点とする二分木が与えられます。各ノードの「深さ」とは、そのノードからルートまでの最短距離のことで、木全体の中で最大の深さを持つノードを「最も深いノード」と呼びます。また、あるノードの「部分木」とは、そのノード自身とそのすべての子孫からなる集合のことです。

この問題では、すべての最も深いノードをその部分木に含むようなノード、すなわち最小の共通部分木の根となるノードを求めます。

たとえば、次のような二分木が与えられたとします。

このとき、求めるべき最小の部分木は次のようになります。

解法のアプローチ

この問題は、再帰的な深さ優先探索（DFS）を使うことで効率的に解けます。ポイントは、各ノードに対して「(答えの候補ノード, その深さ)」というペアを返す補助関数 solve() を定義することです。手順は以下の通りです。

• solve() メソッドを定義し、引数として root を受け取ります。
• root が NULL の場合は、ペア (NULL, 0) を返します。
• l := solve(root の左部分木)、r := solve(root の右部分木) として再帰的に計算します。
• 左側の深さ（2番目の値）が右側より大きい場合：(l の1番目の値, l の深さ + 1) を返します。
• 左側の深さが右側より小さい場合：(r の1番目の値, r の深さ + 1) を返します。
• 両者の深さが等しい場合：左右どちらかに偏ることなく、現在のノード自体が答えとなるため (root, l の深さ + 1) を返します。
• メイン処理では solve(root) を呼び出し、その結果の1番目の値（ノード）を返します。

この方法なら木を一度たどるだけで答えが得られ、時間計算量は O(n)、空間計算量は O(h)（h は木の高さ）に抑えられます。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = 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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      } else {
         if(curr->left)
         q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr->val == 0 || curr == NULL){
            cout << "null" << ", ";
         } else {
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   pair <TreeNode*, int> solve(TreeNode* root){
      if(!root || root->val == 0) return {NULL, 0};
      pair <TreeNode*, int> L = solve(root->left);
      pair <TreeNode*, int> R = solve(root->right);
      if(L.second > R.second)return {L.first, L.second + 1};
      else if(L.second < R.second) return {R.first, R.second + 1};
      return {root, L.second + 1};
   }
   TreeNode* subtreeWithAllDeepest(TreeNode* root) {
      return solve(root).first;
   }
};
main(){
   vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   tree_level_trav(ob.subtreeWithAllDeepest(root)) ;
}

入力

{3,5,1,6,2,0,8,NULL,NULL,7,4}

出力

[2,7,4]

出力の解説

この例では、木全体で最も深いノードは 7 と 4 です。これら両方を部分木に含む最小のノードは 2 であるため、出力は [2,7,4] となります。solve() 関数が左右の部分木の深さを比較しながら答えを底上げしていくことで、一度の走査で正解のノードを特定できる仕組みです。