如果二叉树表示家谱中男性的血缘结构,某家族需要完成一项危险任务,三代及以上单传的男性不允许报名(该树叶结点的父结点、祖父结点均为独生子结点),能否设计程序,在一棵二叉树中筛选出这些结点。
时间: 2024-02-11 22:08:06 浏览: 90
可以通过递归遍历二叉树的每个节点,然后根据该节点的父亲节点和祖父节点的情况进行筛选。具体的筛选条件为:
- 如果该节点的父节点和祖父节点都为空,则该节点为根节点,跳过。
- 如果该节点的父节点为空,或者其父节点的父节点为空,则该节点为根节点的子节点或孙子节点,跳过。
- 如果该节点的父节点和祖父节点都不为空,且其父节点是其父亲节点的唯一的孩子,则该节点为三代及以上单传的男性,加入结果集合。
下面是C++代码实现:
```c++
void dfs(TreeNode* node, TreeNode* father, TreeNode* grand_father, vector<TreeNode*>& res) {
if (node == nullptr) return;
if (father == nullptr && grand_father == nullptr) {
// 根节点,跳过
dfs(node->left, node, father, res);
dfs(node->right, node, father, res);
} else if (father == nullptr || grand_father == nullptr) {
// 子节点或孙子节点,跳过
dfs(node->left, node, father, res);
dfs(node->right, node, father, res);
} else if (father == grand_father->left && grand_father->right == nullptr) {
// 三代及以上单传的男性,加入结果集合
res.push_back(node);
dfs(node->left, node, father, res);
dfs(node->right, node, father, res);
} else {
dfs(node->left, node, father, res);
dfs(node->right, node, father, res);
}
}
vector<TreeNode*> filterNodes(TreeNode* root) {
vector<TreeNode*> res;
dfs(root, nullptr, nullptr, res);
return res;
}
```
该程序的时间复杂度为$O(n)$,其中$n$为二叉树的节点数。
阅读全文