C++の2つの二分木で最初の一致しない葉を見つけます

2つの二分木があるとします。一致しない2本の木の最初の葉を見つける必要があります。一致しない葉がない場合は、何も表示しません。

これらが2つのツリーである場合、最初の一致しない葉は11と15です。

ここでは、スタックを使用して、両方のツリーの反復プレオーダートラバーサルを同時に使用します。ツリーごとに異なるスタックを使用します。トップノードがリーフノードになるまで、ノードをスタックにプッシュします。 2つのトップを比較し、同じ場合はさらにチェックし、そうでない場合は2つのスタックトップ要素を表示します。

例

#include <iostream>
#include <stack>
using namespace std;
class Node {
   public:
   int data;
   Node *left, *right;
};
Node *getNode(int x) {
   Node * newNode = new Node;
   newNode->data = x;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool isLeaf(Node * t) {
   return ((t->left == NULL) && (t->right == NULL));
}
void findUnmatchedNodes(Node *t1, Node *t2) {
   if (t1 == NULL || t2 == NULL)
      return;
   stack<Node*> s1, s2;
   s1.push(t1); s2.push(t2);
   while (!s1.empty() || !s2.empty()) {
      if (s1.empty() || s2.empty() )
         return;
      Node *top1 = s1.top();
      s1.pop();
      while (top1 && !isLeaf(top1)){
         s1.push(top1->right);
         s1.push(top1->left);
         top1 = s1.top();
         s1.pop();
      }
      Node * top2 = s2.top();
      s2.pop();
      while (top2 && !isLeaf(top2)){
         s2.push(top2->right);
         s2.push(top2->left);
         top2 = s2.top();
         s2.pop();
      }
      if (top1 != NULL && top2 != NULL ){
         if (top1->data != top2->data ){
            cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl;
               return;
         }
      }
   }
}
int main() {
   Node *t1 = getNode(5);
   t1->left = getNode(2);
   t1->right = getNode(7);
   t1->left->left = getNode(10);
   t1->left->right = getNode(11);
   Node * t2 = getNode(6);
   t2->left = getNode(10);
   t2->right = getNode(15);
   findUnmatchedNodes(t1,t2);
}

出力

First non matching leaves are: 11 15