收获:初次接触了解pair,对于DFS和BFS有了深入一点点的认识
过程:开始自己尝试写,完全没有使用DFS和BFS的想法,自己写了半个多小时,却都编译不过,尝试根据完全二叉树来做,计算了半天,发现不好确定节点深度。无果,查看题解。
答题思路使用DFS或者是BFS,虽然我刚刚学过,可是根本没有使用的思路,使用了BFS,研究了一下代码,对照着敲了出来,可是运行时间为12s,后来直接复制大佬的,4s。。。。。。
class Solution {
public:
using PTT = pair<TreeNode*, TreeNode*>;
bool isCousins(TreeNode* root, int x, int y) {
// 使用队列q来进行bfs
// 其中pair中,p.first 记录当前结点的指针,p.second 记录当前结点的父结点的指针
queue<PTT> q;
q.push({root, nullptr});
while(!q.empty()) {
int n = q.size();
vector<TreeNode*> rec_parent;
for(int i = 0; i < n; i++) {
auto [cur, parent] = q.front(); q.pop();
if(cur->val == x || cur->val == y)
rec_parent.push_back(parent);
if(cur->left) q.push({cur->left, cur});
if(cur->right) q.push({cur->right, cur});
}
// `x` 和 `y` 都没出现
if(rec_parent.size() == 0)
continue;
// `x` 和 `y` 只出现一个
else if(rec_parent.size() == 1)
return false;
// `x` 和 `y` 都出现了
else if(rec_parent.size() == 2)
// `x` 和 `y` 父节点 相同/不相同 ?
return rec_parent[0] != rec_parent[1];//在这里也学到了点简化代码的的技巧
}
return false;
}
};