检查两棵树是否彼此镜像

在本教程中，我们将看到如何检查2棵树是否彼此镜像。

问题陈述：

您将获得2棵树的根节点。您需要检查这两棵树是否彼此镜像。

例如：

下面两棵树是彼此镜像的。

如上所示，除根节点外，左子节点将变为右节点，反之亦然。这就是二叉树镜像的含义。

从上面的图像中，我们可以得出以下返回true的点。

1. 如果当前是根节点，则继续。
2. 如果树1的左孩子等于右孩子值，则返回true。
3. 如果右子级值等于左子级值，则返回true。
4. 如果两者均为NULL，则返回true。

我们还可以在下面定义错误的陈述：

1. 如果树1中存在正确的子级，树2中没有子级返回false，反之亦然。
2. 如果右子级值与树2的左子级值不同，则返回false。

C ++解决方案

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


bool check_if_mirror(Node *node1, Node *node2) 
{
    if (node1 == NULL && node2 == NULL) 
    {
      return true;
    }

    if (node1 == NULL || node2 == NULL) 
    {
      return false;
    }

    return node1->data == node2->data 
        && check_if_mirror(node1->left, node2->right) 
        && check_if_mirror(node1->right, node2->left);
  }


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);



    Node* root_1 = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          25      10
         /  \    /  \
        /    \  /    \
       30    18 15     7

    */

    root_1 = new Node(16);
    root_1->left = new Node(25);
    root_1->right = new Node(10);
    root_1->left->left = new Node(30);
    root_1->left->right = new Node(18);
    root_1->right->left = new Node(15);
    root_1->right->right = new Node(7);

    if(check_if_mirror(root, root_1))
    {
        cout<<"Both are mirror"<<endl;
    } else {
        cout<<"Both are not mirror"<<endl;
    }

    return 0;  
}

输出：

Both are mirror

该网站上可用的教程列表：