Point2OfferCode/26_SubTree.cpp at master · slientreed/Point2OfferCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

//
//  Created by mark on 2019/7/8.
//  Copyright © 2019年 mark. All rights reserved.
//

/*
 说明：
 1. 问题：26.树的子结构，判断树B，是不是树A的子结构
 2. 思路：递归
        1. 遍历树A，查找与B的根节点一样的节点
        2. 判断数A中以R节点为根节点的子树，是不是和B有相同的结构。
 */


#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>

using namespace std;


struct BinaryTreeNode
{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
}TN,*pTN;

bool isSubTree(BinaryTreeNode* rootA, BinaryTreeNode* rootB);

// 步骤1. 在A中查找和B根节点一样的节点
bool HasSubTree(BinaryTreeNode* rootA, BinaryTreeNode* rootB)
{
    bool res = false;

    if(rootA != nullptr && rootB != nullptr)
    {
        if(rootA->val == rootB->val)
            res = isSubTree(rootA,rootB);

        if(!res)
            res = HasSubTree(rootA->left, rootB) || HasSubTree(rootA->right, rootB);    // 递归
    }

    return res;
}


// 步骤2. 判断A中以R为根节点的子树是不是和B同构
bool isSubTree(BinaryTreeNode* rootA, BinaryTreeNode* rootB)
{
    if(rootB == nullptr)
        return true;
    if(rootA == nullptr)
        return false;

    if(rootA->val != rootB->val)
        return false;

    return isSubTree(rootA->left, rootB->left) && isSubTree(rootA->right, rootB->right);   // 递归左右子树
}


//辅助函数 ------------------------------------------------------------------------------------------------------------------------

// 构建树节点
BinaryTreeNode* CreateTreeNode(int val)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->val = val;
    pNode->left = nullptr;
    pNode->right = nullptr;

    return pNode;
}

// 连接树节点
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}


// 销毁树
void DestroyTree(BinaryTreeNode* root)
{
    if(root != nullptr)
    {
        BinaryTreeNode* left = root->left;
        BinaryTreeNode* right = root->right;

        delete root;
        root = nullptr;

        DestroyTree(left);
        DestroyTree(right);
    }
}


int main(){

    // 创建两个树
    /*
                      1                      2
                2          3              4     5
             4     5

     */

    BinaryTreeNode* A1 = CreateTreeNode(1);
    BinaryTreeNode* A2 = CreateTreeNode(2);
    BinaryTreeNode* A3 = CreateTreeNode(3);
    BinaryTreeNode* A4 = CreateTreeNode(4);
    BinaryTreeNode* A5 = CreateTreeNode(5);
    ConnectTreeNodes(A1, A2, A3);
    ConnectTreeNodes(A2, A4, A5);

    BinaryTreeNode* B1 = CreateTreeNode(2);
    BinaryTreeNode* B2 = CreateTreeNode(6);
    BinaryTreeNode* B3 = CreateTreeNode(5);
    ConnectTreeNodes(B1, B2, B3);

    if(HasSubTree(A1, B1))
        cout << "B是A的子树" << endl;
    else
        cout << "B不是A的子树" << endl;

    return 0;
}