树同构问题详解

给定两个二叉树，我们的任务是检查它们是否同构。如果一棵树能够通过一系列翻转操作（即交换若干节点的左右子节点）变成另一棵树，我们称这两棵树是同构的。任何层级的任意数量的节点都可以进行子节点交换。

注意：

• 如果两棵树完全相同（结构和节点值都相同），它们也是同构的。
• 两个空树是同构的。
• 如果两棵树的根节点值不同，则它们不是同构的。

示例：

> 输入：

> !Tree-Isomorphism-Problem

> 输出： True

> 解释： 上述两棵树是同构的，其中翻转了以下子树：2 和 3，NULL 和 6，7 和 8。

在练习平台上尝试

目录

• [预期方法 – 1] 使用递归 – O(n) 时间和 O(n) 空间
• [预期方法 – 2] 使用迭代 – O(n) 时间和 O(n) 空间

[预期方法 – 1] 使用递归 – O(n) 时间和 O(n) 空间

> 核心思路是递归地遍历两棵树，对比节点 n1 和 n2。它们的数据必须相同，且它们的子树要么完全相同，要么互为镜像（即被翻转过）。这确保了树在结构上是同构的。

让我们按照以下步骤来解决这个问题：

假设两棵树当前的内部节点分别为 n1 和 n2。为了使以 n1 和 n2 为根的子树同构，必须满足以下条件：

• n1 和 n2 的 data（数据）必须 相同。
• n1 和 n2 的子节点 children 必须满足以下两个条件之一：

– n1 的左子节点与 n2 的左子节点同构，且 n1 的右子节点与 n2 的右子节点同构。

– n1 的左子节点与 n2 的右子节点同构，且 n1 的右子节点与 n2 的左子节点同构。

这确保了树要么在结构上完全一致，要么在某些层级上被“翻转”过，但依然是同构的。

下面是该方法的实现代码：

C++

// C++ code to check if two trees are 
// isomorphic using recursion
#include 
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;

    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to check if two trees are isomorphic
bool isIsomorphic(Node* root1, Node* root2) {
  
    // Both roots are NULL, trees are isomorphic
    // by definition
    if (root1 == nullptr && root2 == nullptr) {
        return true;
    }

    // Exactly one of the root1 and root2 is NULL, 
    // trees not isomorphic
    if (root1 == nullptr || root2 == nullptr) {
        return false;
    }

    // If the data doesn‘t match, trees 
    // are not isomorphic
    if (root1->data != root2->data) {
        return false;
    }

    // Check if the trees are isomorphic by 
    // considering the two cases:
    // Case 1: The subtrees have not been flipped
    // Case 2: The subtrees have been flipped
    return (isIsomorphic(root1->left, root2->left) &&
            isIsomorphic(root1->right, root2->right)) ||
           (isIsomorphic(root1->left, root2->right) &&
            isIsomorphic(root1->right, root2->left));
}

int main() {
  
    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    //       / \
    //      7   8
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
    root1->left->right->left = new Node(7);
    root1->left->right->right = new Node(8);

    // Representation of input binary tree 2
    //        1
    //       / \
    //      3   2
    //     /   / \
    //    6   4   5
    //           / \
    //          8   7
    Node* root2 = new Node(1);
    root2->left = new Node(3);
    root2->right = new Node(2);
    root2->left->left = new Node(6);
    root2->right->left = new Node(4);
    root2->right->right = new Node(5);
    root2->right->right->left = new Node(8);
    root2->right->right->right = new Node(7);

    if (isIsomorphic(root1, root2)) {
        cout << "True
";
    }
    else {
        cout << "False
";
    }

    return 0;
}

Java

“`

// Java code to check if two trees are

// isomorphic using recursion

import java.util.*;

class Node {

int data;

Node left, right;