C++刷剑指offer（面试题26. 树的子结构）【广度优先搜索】

糖逗

题目描述：

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：

0 <= 节点个数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;

struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(NULL), right(NULL){
        }
};

TreeNode* CreateTree(vector<int> input){
        TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size(); i++){
                res[i].val = input[i];
                res[i].left = NULL;
                res[i].right = NULL;
        }
        for(int i= 0; i < input.size(); i++){
                if(2*i+1 < input.size()){
                        res[i].left = &res[2*i+1];
                }
                if(2*i+2 < input.size()){
                        res[i].right = &res[2*i+2];
                }
                
        }
        return res;
        
}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
           
    middle(root->left, res, left, insert - 1, depth + 1);
    middle(root->right, res, insert + 1, right, depth + 1);
    }

int treeDepth(TreeNode* root){
    if(root == NULL || root -> val == 0) return 0;
    return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
      
void PrintTree(TreeNode* root) {
    int depth = treeDepth(root);
    int width = pow(2, depth) - 1;
    vector<vector<int> > res(depth, vector<int>(width, 0));
    middle(root, res, 0, width - 1, 0);
    for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                       
                }
                cout << endl;
        }
        cout << "------------------" << endl;
    }


TreeNode* findNode(TreeNode* A, TreeNode* B){
        if(A == NULL) return A;
        queue <TreeNode*> temp;
        temp.push(A);
        while(!temp.empty()){
                auto node = temp.front();
                temp.pop();
                if(node -> val == B -> val) return node;
                if(node ->left != NULL) temp.push(node->left);
                if(node -> right != NULL) temp.push(node -> right);
        }
        return NULL;
}





bool solution(TreeNode*A, TreeNode*B){
        if(A == NULL&& B!= NULL) return false;
    if(A != NULL && B == NULL) return true;
    if(A==NULL && B ==NULL) return true;
    if(A->val != B->val) return false;
    return solution(A->right,B->right) && solution(A->left, B->left);
}

bool isSubStructure(TreeNode*A, TreeNode*B){
    if(A!=NULL && B==NULL) return false;
    TreeNode* node = findNode(A, B);
    return solution(node, B);
    
}

int main(void){
        vector<int> input1, input2;
        cout << "send numbers for the first tree" << endl;
        int number1;
        while(cin >> number1){
                input1.push_back(number1); 
        }
        cin.clear();
        cout << "send numbers for the second tree" << endl;
        int number2;
        while(cin >> number2){
                input2.push_back(number2); 
        }
        
        TreeNode* root1 = CreateTree(input1);
        PrintTree(root1);
        
        TreeNode* root2 = CreateTree(input2);
        PrintTree(root2);
       
                bool res =  isSubStructure(root1, root2);
                cout << res << endl;
        return 0;
}

注意事项：
1.解题思路：分两步，先找到A中包含B根节点的子节点，然后再递归比较A的子树C和B，判断B是否是C的子树。
2.第一步找子节点用到广度优先搜索。

糖逗

核心代码：

TreeNode* findNode(TreeNode* A, TreeNode* B){
        if(A == NULL) return A;
        queue <TreeNode*> temp;
        temp.push(A);
        while(!temp.empty()){
                auto node = temp.front();
                temp.pop();
                if(node -> val == B -> val) return node;
                if(node ->left != NULL) temp.push(node->left);
                if(node -> right != NULL) temp.push(node -> right);
        }
        return NULL;
}



bool solution(TreeNode*A, TreeNode*B){
        if(A == NULL&& B!= NULL) return false;
    if(A != NULL && B == NULL) return true;
    if(A==NULL && B ==NULL) return true;
    if(A->val != B->val) return false;
    return solution(A->right,B->right) && solution(A->left, B->left);
}

bool isSubStructure(TreeNode*A, TreeNode*B){
    if(A!=NULL && B==NULL) return false;
    TreeNode* node = findNode(A, B);
    return solution(node, B);
   
}

糖逗