C++で2つの二分木をマージするプログラム

2つの二分木があり、一方をもう一方を覆うように配置すると、2つのツリーの一部のノードがオーバーラップし、他のノードがオーバーラップするとします。それらを新しいバイナリツリーにマージする必要があります。マージルールは、2つのノードがオーバーラップしている場合、ノード値を合計して、マージされたノードの新しい値として計算するようなものです。それ以外の場合は、空でないノードが新しいツリーのノードとして使用されます。

したがって、木が-

その場合、出力は-

これを解決するには、次の手順に従います-

• メソッドはsolve（）です。これは、2つのツリーノードn1とn2を取ります。これは次のようなものです
• n1が空で、n2が空でない場合は、n2を返します。それ以外の場合は、n2が空で、n1が空でない場合は、n1を返し、両方がnullの場合は、nullを返します。
• n1の値：=n1の値+n2の値
• n1の左側：=解決（n1の左側、n2の左側）
• n1の権利：=解決（n1の権利、n2の権利）
• n1を返す

理解を深めるために、次の実装を見てみましょう-

例

#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int v){
      val = v;
      left = right = NULL;
   }
};
void inord(TreeNode *root) {
   if (root != NULL) {
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
public:
   TreeNode* solve(TreeNode* n1, TreeNode* n2) {
      if(!n1 && n2)
         return n2;
      else if(!n2 && n1)
         return n1;
      else if(!n1 && !n2)
         return NULL;
         n1->val+=n2->val;
         n1->left = solve(n1->left,n2->left);
         n1->right = solve(n1->right,n2->right);
         return n1;
   }
};
main(){
   TreeNode *root1 = new TreeNode(1);
   root1->left = new TreeNode(3);
   root1->right = new TreeNode(2);
   root1->left->left = new TreeNode(5);
   TreeNode *root2 = new TreeNode(2);
   root2->left = new TreeNode(1);
   root2->right = new TreeNode(3);
   root2->left->right = new TreeNode(4);
   root2->right->right = new TreeNode(7);
   Solution ob;
   TreeNode *root_res = ob.solve(root1, root2);
   inord(root_res);
}

入力

TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);

出力

5 4 4 3 5 7