剑指Offer算法题-树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

题解

思路是两个树全都先序遍历一下，然后判断B的序列是否是A的子序列即可

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void dfs(TreeNode* root, vector<int> & seq){
        if(!root) return;
        seq.push_back(root->val);
        dfs(root->left, seq);
        dfs(root->right,seq);
    }
    bool isInnerSeq(vector<int> & seq1, vector<int> & seq2){
        if(!seq1.size() || !seq2.size()) return false;
        for(int i = 0; i < seq1.size(); i++){
            bool flag = true;
            for(int j = 0; j < seq2.size(); j++)
                if(seq2[j] != seq1[i + j]){
                    flag = false;
                    break;
                }
            if(flag) return true;
        }
        return false;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        vector<int> PreA, PreB;
        dfs(pRoot1, PreA);
        dfs(pRoot2, PreB);
        return isInnerSeq(PreA, PreB);
    }
};