检查一棵二叉树是否为另一棵二叉树的子树

给定两棵二叉树，我们的任务是检查第一棵树是否是第二棵树的子树。一棵树 T(root1) 的子树是指另一棵树 S(root2)，它由 T 中的一个节点及其在 T 中的所有后代组成。与根节点对应的子树是整棵树，而与其他任何节点对应的子树则被称为真子树。

示例：

> 输入：

> !Check-if-a-Binary-Tree-is-subtree-of-another-binary-tree

> 输出： True

> 解释： root2 是 root1 的子树。

> 在练习题目中试一试<img src="https://www.geeksforgeeks.org/problems/check-if-subtree/1" alt="重定向图标" />

方法：

> 这种朴素方法背后的思路是，在主树的每一个节点处检查，是否存在与给定的子树相匹配的子树。

请按照以下步骤解决问题：

• 以先序方式遍历以 root1 为根的树。
• 对于遍历过程中的每一个被访问的节点，检查以该节点为根的子树是否与以 root2 为根的树完全相同。
• 为了检查子树是否相同，我们需要同时遍历两棵树。
• 如果某个被访问节点的值与另一棵树中对应节点的值不相等，则返回 false。否则，继续遍历，直到验证完整个子树。

下面是上述方法的实现：

C++

// C++ Program to Check if a Binary Tree is subtree
// of another binary tree 

#include 

using namespace std;

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

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

// Utility function to check if two trees are identical
bool areIdentical(Node* root1, Node* root2) {
    if (root1 == nullptr && root2 == nullptr)
        return true;
    if (root1 == nullptr || root2 == nullptr)
        return false;

    // Check if data and left/right subtrees are identical
    return (root1->data == root2->data &&
            areIdentical(root1->left, root2->left) &&
            areIdentical(root1->right, root2->right));
}

// Function to check if root2 is a subtree of root1
bool isSubtree(Node* root1, Node* root2) {
    if (root2 == nullptr)
        return true; 
    if (root1 == nullptr)
        return false; 
  
    // Check if the current node of root1 matches 
  	// the root of root2
    if (areIdentical(root1, root2))
        return true;

    // Recur for left and right subtrees of root1
    return isSubtree(root1->left, root2) 
      || isSubtree(root1->right, root2);
}

int main() {
  
    // Construct Tree root1
    //          26
    //         /  \
    //        10   3
    //       / \    \
    //      4   6    3
    //       \
    //        30
    Node* root1 = new Node(26);
    root1->right = new Node(3);
    root1->right->right = new Node(3);
    root1->left = new Node(10);
    root1->left->left = new Node(4);
    root1->left->left->right = new Node(30);
    root1->left->right = new Node(6);

    // Construct Tree root2
    //          10
    //         /  \
    //        4    6
    //         \
    //          30
    Node* root2 = new Node(10);
    root2->right = new Node(6);
    root2->left = new Node(4);
    root2->left->right = new Node(30);

    if (isSubtree(root1, root2))
        cout << "true";
    else
        cout << "false";

    return 0;
}

“

// C Program to Check if a Binary Tree is

// subtree of another binary tree

#include

#include

struct Node {

int data;

struct Node* left;

struct Node* right;

};

// Utility function to check if two trees are identical

int areIdentical(struct Node root1, struct Node root2) {

if (root1 == NULL && root2 == NULL)

return 1;

if (root1 == NULL || root2 == NULL)

return 0;

// Check if data and left/right subtrees are identical

return (root1->data == root2->data &&

areIdentical(root1->left, root2->left) &&

areIdentical(root1->right, root2->right));

}

// Function to check if root2 is a subtree of root1

int isSubtree(struct Node root1, struct Node root2) {

if (root2 == NULL)

return 1;

if (root1 == NULL)

return 0;

// Check if the current node of root1 matches

// the root of root2

if (areIdentical(root1, root2))

return 1;

// Recur for left and right subtrees of root1

return isSubtree(root1->left, root2)

|| isSubtree(root1->right, root2);

}

struct Node* createNode(int value) {

struct Node* newNode =

(struct Node*)malloc(sizeof(struct Node));

newNode->data = value;