C++의 두 이진 트리에서 일치하지 않는 첫 번째 잎 찾기

두 개의 이진 트리가 있다고 가정합니다. 일치하지 않는 두 나무의 첫 번째 잎을 찾아야 합니다. 일치하지 않는 잎이 없으면 아무 것도 표시하지 않습니다.

이것이 두 개의 나무인 경우 첫 번째 일치하지 않는 잎은 11과 15입니다.

여기서 우리는 스택을 사용하여 동시에 두 트리의 반복적인 선주문 순회를 사용할 것입니다. 우리는 다른 나무에 대해 다른 스택을 사용할 것입니다. 최상위 노드가 리프 노드가 될 때까지 스택에 노드를 푸시합니다. 두 개의 상단을 비교하고 동일하면 추가 확인을 수행하고 그렇지 않으면 두 개의 스택 상단 요소를 표시합니다.

예시

#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