方法一:广度优先搜索
堂兄弟结点主要满足以下两个条件:
- 在同一层;
- 父亲结点不同;
因而可以通过广度优先搜索用一个map来将一个结点的value,所在层数和其父亲结点记录下来,最后在判断题目所给的两个结点是否满足堂兄弟结点的两个条件。
1.3 问题解决class Solution { public: bool isCousins(TreeNode* root, int x, int y) { map二、Leetcode-572:另一棵树的子树 2.1 问题描述 2.2 问题分析> 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; } };
方法一:暴力枚举
通过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); } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)