2021-11-10每日刷题打卡

2021-11-10每日刷题打卡 一、Leetcode-993：二叉树的堂兄弟节点 1.1 问题描述

1.2 问题分析

方法一：广度优先搜索

堂兄弟结点主要满足以下两个条件：

1. 在同一层；
2. 父亲结点不同；

因而可以通过广度优先搜索用一个map来将一个结点的value，所在层数和其父亲结点记录下来，最后在判断题目所给的两个结点是否满足堂兄弟结点的两个条件。

1.3 问题解决

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        map> m;
        queue q;
        int level = 0;

        if(root != nullptr) q.push(root);

        while(!q.empty())
        {
            int n = q.size();
            while(n--)
            {
                TreeNode* node = q.front();
                q.pop();
                if(node->left != nullptr) { q.push(node->left); m[node->left->val] = make_pair(level+1, node); }
                 if(node->right != nullptr) { q.push(node->right); m[node->right->val] = make_pair(level+1, node); }
            }
            level++;
        }

        if(m[x].first == m[y].first)
        {
            if(m[x].second != m[y].second)
                return true;
            else
                return false;
        }
        else
            return false;
    }
};

二、Leetcode-572：另一棵树的子树 2.1 问题描述

2.2 问题分析

方法一：暴力枚举

通过dfs来遍历root树的每个结点的同时，检查遍历到的当前结点所组成的子树和subRoot树是否结构相同

2.3 问题解决

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if(p == nullptr && q == nullptr) return true;

        if((p != nullptr && q == nullptr) || (p == nullptr && q != nullptr) || (p->val != q->val))
            return false;
        
        return check(p->left, q->left) && check(p->right, q->right);
    }

    bool dfs(TreeNode *p, TreeNode *q) {
        if(p == nullptr) return false;

        return check(p, q) || dfs(p->left, q) || dfs(p->right, q);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        return dfs(root, subRoot);
    }
};