给你一棵二叉树的扩展后序遍历序列,求这棵二叉树中某个结点的子孙结点个数(包括孩子结点)c++
时间: 2023-07-16 16:11:46 浏览: 71
我们可以通过扩展后序遍历序列来还原二叉树,然后进行深度优先搜索,统计目标结点的子孙结点个数。
具体步骤如下:
1. 根据扩展后序遍历序列还原二叉树。我们可以使用一个栈来记录当前未处理的结点,具体的还原方法可以参考这篇文章:[如何根据扩展后序遍历还原二叉树](https://www.cnblogs.com/TenosDoIt/p/3661694.html)。
2. 进行深度优先搜索。从根结点开始,递归地遍历左右子树,统计目标结点的子孙结点个数。如果当前结点是目标结点,那么直接返回它的子孙结点个数;否则,返回左右子树中目标结点的子孙结点个数之和加上当前结点自身。
下面是实现代码:
```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 根据扩展后序遍历序列还原二叉树
TreeNode* buildTree(vector<int>& postorder) {
if (postorder.empty()) {
return NULL;
}
stack<TreeNode*> stk;
int n = postorder.size();
for (int i = 0; i < n; i++) {
TreeNode* cur = new TreeNode(postorder[i]);
if (cur->val < 0) {
cur->right = stk.top();
stk.pop();
cur->left = stk.top();
stk.pop();
}
stk.push(cur);
}
return stk.top();
}
// 深度优先搜索统计子孙结点个数
int countDescendants(TreeNode* root, int target) {
if (root == NULL) {
return 0;
}
if (root->val == target) {
// 如果当前结点是目标结点,直接返回它的子孙结点个数
int leftDescendants = root->left ? countDescendants(root->left, target) + 1 : 1;
int rightDescendants = root->right ? countDescendants(root->right, target) + 1 : 1;
return leftDescendants + rightDescendants - 1;
}
else {
// 否则,返回左右子树中目标结点的子孙结点个数之和加上当前结点自身
return countDescendants(root->left, target) + countDescendants(root->right, target);
}
}
int main() {
vector<int> postorder = { 2, 3, 1, -1, -1, 4, 5, -1, -1, 6, -1, -1, 7, -1, -1 };
TreeNode* root = buildTree(postorder);
int target = 1;
int ans = countDescendants(root, target);
cout << "The number of descendants of " << target << " is " << ans << endl;
return 0;
}
```