C++で2つの二分探索木の全要素を昇順リストとして取得する方法

問題の概要

2つの二分探索木（BST：Binary Search Tree）が与えられたとき、両方の木に含まれるすべての要素を昇順に並べたリストを返すことを考えます。

例えば、次のような2つの二分探索木があるとします。

木1：[2,1,4]
木2：[1,0,3]

この場合、出力は [0,1,1,2,3,4] となります。重複する値（この例では「1」）もそのまま保持される点に注意してください。

解決のためのアプローチ

この問題は、各BSTに対して反復的な中順走査（inorder traversal）を行い、マージソートのように2つの走査結果を統合することで効率的に解けます。手順は以下の通りです。

• 結果を格納する配列 ans を定義し、補助用の2つのスタック st1 と st2 を用意します。
• curr1 := root1、curr2 := root2 とします。
• ルート1とその左側のノードすべてを st1 に、ルート2とその左側のノードすべてを st2 にプッシュします。
• st1 または st2 のどちらかが空でない限り、以下を繰り返します。
  • st1 が空でなく、かつ（st2 が空である、または st1 の先頭ノードの値 ≤ st2 の先頭ノードの値）の場合：
    • temp := st1 の先頭ノードとし、st1 からポップします。
    • temp の値を ans に追加します。
    • temp の右部分木およびその左側ノードすべてを st1 にプッシュします。
  • それ以外の場合：
    • temp := st2 の先頭ノードとし、st2 からポップします。
    • temp の値を ans に追加します。
    • temp の右部分木およびその左側ノードすべてを st2 にプッシュします。
• 最後に ans を返します。

この手法により、各木の中順走査が自然に昇順の値列を生成する性質を利用しながら、2つのソート済みシーケンスを1つにマージできます。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
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:
   void pushLeft(stack <TreeNode*>& st, TreeNode* root){
      TreeNode* curr = root;
      while(curr){
         st.push(curr);
         curr = curr->left;
      }
   }
   vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
      vector <int> ans;
      stack <TreeNode*> st1, st2;
      TreeNode* curr1 = root1;
      TreeNode* curr2 = root2;
      pushLeft(st1, curr1);
      pushLeft(st2, curr2);
      while(!st1.empty() || !st2.empty()){
         TreeNode* temp;
         if(!st1.empty() && (st2.empty() || st1.top()->val <= st2.top()->val)){
            temp = st1.top();
            st1.pop();
            ans.push_back(temp->val);
            pushLeft(st1, temp->right);
         }
         else{
            temp = st2.top();
            st2.pop();
            ans.push_back(temp->val);
            pushLeft(st2, temp->right);
         }
      }
      return ans;
   }
};
main(){
   vector<int> v = {2,1,4};
   TreeNode *root1 = make_tree(v);
   v = {1,0,3};
   TreeNode *root2 = make_tree(v);
   Solution ob;
   print_vector(ob.getAllElements(root1, root2));
}

入力

[2,1,4]
[1,0,3]

出力

[0,1,1,2,3,4]

計算量について

このアルゴリズムでは、各ノードをちょうど1回ずつ訪問するため、時間計算量は O(m + n)（m、n はそれぞれ2つの木のノード数）となります。また、スタックには最大で木の高さ分のノードが保持されますが、最悪の場合の空間計算量も O(m + n) です。再帰を使わない反復処理のため、深い木でもスタックオーバーフローの心配が少ないのも利点です。