Cây đối xứng trong C ++

Giả sử chúng ta có một cây nhị phân và nhiệm vụ là kiểm tra xem nó có xây dựng một đối xứng của chính nó hay không. Cây nhị phân đối xứng xây dựng hình ảnh phản chiếu của chính nó.

Ví dụ

Đầu vào-1:

Đầu ra:

True

Giải thích:

Vì cây nhị phân đã cho xây dựng hình ảnh phản chiếu của chính nó, nên kết quả đầu ra là True.

Đầu vào-2:

Đầu ra:

False

Giải thích:

Vì cây nhị phân đã cho không tạo ra hình ảnh phản chiếu của chính nó, nên nó không đối xứng.

Phương pháp tiếp cận để giải quyết vấn đề này

Cây nhị phân đối xứng là cây là hình ảnh phản chiếu của chính nó, có nghĩa là chúng ta phải kiểm tra xem các nút bên trái và bên phải của cây có giống nhau hay không.

Một hàm Boolean ban đầu sẽ kiểm tra nút bên trái và nút bên phải. Nếu các nút trống hoặc NULL, thì nó sẽ trả về True. Đối với các trường hợp khác, chúng tôi sẽ kiểm tra xem nó có con bên trái hay bên phải, sau đó nó phải giống nhau để nó sẽ là Cây đối xứng.

• Lấy một Cây nhị phân có chứa gốc và con của nó.
• Trình trợ giúp chức năng trợ giúp Boolean (nút * root1, nút * root2) lấy hai gốc của cùng một cây, giúp kiểm tra xem cây con bên trái và con bên phải có giống nhau hay không.
• Nếu cây trống hoặc NULL, thì chúng tôi sẽ trả về True.
• Kiểm tra đệ quy xem nút bên trái và nút bên phải của cây có bằng nhau hay không.
• Trả về False nếu tất cả các điều kiện trên không thỏa mãn.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
bool helper(struct treenode * root1, struct treenode * root2) {
   if (root1 == NULL and root2 == NULL)
      return true;
   if (root1 and root2 and root1 -> data == root2 -> data)
      return (helper(root1 -> left, root2 -> right) and helper(root1 -> right, root2 -> left));
   return false;
}
bool isSymmetry(struct treenode * root) {
   return helper(root, root);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   if (isSymmetry(root)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

Chạy đoạn mã trên sẽ tạo ra kết quả là,

Đầu ra

False

Giải thích:

Vì cây đã cho không đối xứng nên chúng ta nhận được kết quả là Sai.