Tìm các lá không khớp đầu tiên trong hai cây nhị phân trong C ++

Giả sử chúng ta có hai cây nhị phân. Chúng ta phải tìm lá đầu tiên của hai cây không trùng nhau. Nếu không có lá nào không phù hợp thì không hiển thị gì.

Nếu đây là hai cây thì số lá không trùng nhau đầu tiên là 11 và 15.

Ở đây, chúng tôi sẽ sử dụng trình duyệt lặp đặt hàng trước lặp đi lặp lại của cả hai cây cùng một lúc bằng cách sử dụng ngăn xếp. Chúng tôi sẽ sử dụng ngăn xếp khác nhau cho các cây khác nhau. Chúng tôi sẽ đẩy các nút vào ngăn xếp cho đến khi nút trên cùng là nút lá. So sánh hai phần tử trên cùng, nếu chúng giống nhau, sau đó kiểm tra thêm, nếu không, hãy hiển thị hai phần tử trên cùng của ngăn xếp.

Ví dụ

#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);
}

Đầu ra

First non matching leaves are: 11 15