判断t1树中是否有与t2树完全相同的子树

C++ 解法, 执行用时: 44ms, 内存消耗: 15372KB, 提交时间: 2021-08-24

/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * };
 */
static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if(!root1)    return !root2;
        if(!root2)    return true;
        return preOrder(root1, root2);
    }
    bool preOrder(TreeNode *root1,TreeNode *root2)
    {
        return isInclude(root1, root2)||root1->left&&preOrder(root1->left, root2)||root1->right&&preOrder(root1->right, root2);
    }
    bool isInclude(TreeNode *root1,TreeNode *root2)
    {
        if(!root1)    return !root2;
        if(!root2||root1->val!=root2->val)    return false;
        return isInclude(root1->left, root2->left)&&isInclude(root1->right, root2->right);
    }
};

C++ 解法, 执行用时: 44ms, 内存消耗: 15448KB, 提交时间: 2021-10-11

/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * };
 */
static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        if(!root1)    return !root2;
        if(!root2)    return true;
        return preOrder(root1, root2);
    }
    bool preOrder(TreeNode *root1,TreeNode *root2) {
        return isInclude(root1, root2)||root1->left&&preOrder(root1->left, root2)||root1->right&&preOrder(root1->right, root2);
    }
    bool isInclude(TreeNode *root1, TreeNode *root2) {
        if(!root1)    return !root2;
        if(!root2||root1->val!=root2->val)    return false;
        return isInclude(root1->left, root2->left)&&isInclude(root1->right, root2->right);
    }
};

C++ 解法, 执行用时: 45ms, 内存消耗: 15340KB, 提交时间: 2021-07-15

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if( !root1 ) return !root2;
        if( !root2 ) return true;
        return preOrderTraversal(root1, root2);
    }
    
    bool preOrderTraversal(TreeNode *root1, TreeNode *root2)
    {
        return isInclude(root1, root2) || 
                root1->left && preOrderTraversal(root1->left, root2) || 
                root1->right && preOrderTraversal(root1->right, root2);
    }
    bool isInclude(TreeNode *root1, TreeNode *root2)
    {
        if( !root1 ) return !root2;
        if(!root2 || root1->val!=root2->val) return false;
        return isInclude(root1->left, root2->left) && isInclude(root1->right, root2->right);
    }
};

C++ 解法, 执行用时: 46ms, 内存消耗: 15372KB, 提交时间: 2021-09-29

/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * };
 */
static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if(!root1)    return !root2;
        if(!root2)    return true;
        return preOrder(root1, root2);
    }
    bool preOrder(TreeNode *root1,TreeNode *root2){
        return isInclude(root1, root2)||root1->left&&preOrder(root1->left, root2)||root1->right&&preOrder(root1->right, root2);
    }
    bool isInclude(TreeNode *root1,TreeNode *root2)
    {
        if(!root1)    return !root2;
        if(!root2||root1->val!=root2->val)    return false;
        return isInclude(root1->left, root2->left)&&isInclude(root1->right, root2->right);
    }
};

C++ 解法, 执行用时: 47ms, 内存消耗: 17348KB, 提交时间: 2021-07-19

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root1 TreeNode类
     * @param root2 TreeNode类
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if( !root1 ) return !root2;
        if( !root2 ) return true;
        return preOrderTraversal(root1, root2);
    }
     
    bool preOrderTraversal(TreeNode *root1, TreeNode *root2)
    {
        return isInclude(root1, root2) ||
                root1->left && preOrderTraversal(root1->left, root2) ||
                root1->right && preOrderTraversal(root1->right, root2);
    }
    bool isInclude(TreeNode *root1, TreeNode *root2)
    {
        if( !root1 ) return !root2;
        if(!root2 || root1->val!=root2->val) return false;
        return isInclude(root1->left, root2->left) && isInclude(root1->right, root2->right);
    }
};

详情