给定二叉搜索树的后序遍历结果,求该树根节点到所有叶子节点的路径及该路径上节点的和,约定树的节点总数不超过1000个。输入格式: 二叉搜索树的后序遍历序列。 输出格式: 根节点到所有叶子节点的路径及路径上所有节点的和。结尾无空格。写出代码c++
时间: 2024-03-24 07:35:49 浏览: 14
以下是求解二叉搜索树后序遍历的根节点到所有叶子节点的路径及路径上所有节点的和的C++代码:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int postorder[N];
int path[N], idx;
int n;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode *buildTree(int left, int right)
{
if (left > right) return nullptr;
TreeNode *root = new TreeNode(postorder[right]);
int k = left;
while (k < right && postorder[k] < postorder[right]) k++;
root->left = buildTree(left, k - 1);
root->right = buildTree(k, right - 1);
return root;
}
void dfs(TreeNode *root, int sum)
{
if (!root) return;
sum += root->val;
path[idx++] = root->val;
if (!root->left && !root->right)
{
for (int i = 0; i < idx; i++)
{
if (i) cout << ' ';
cout << path[i];
}
cout << endl << sum << endl;
}
dfs(root->left, sum);
dfs(root->right, sum);
idx--;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> postorder[i];
TreeNode *root = buildTree(0, n - 1);
dfs(root, 0);
return 0;
}
```
思路:根据二叉搜索树的性质,后序遍历序列的最后一个数为根节点,将其分为左子树和右子树,递归构建二叉搜索树。使用深度优先搜索遍历每个节点,记录下路径和路径上的节点值,当遍历到叶子节点时,输出路径和路径上的节点值的和。由于是深度优先搜索,需要记录下每个节点在路径上的位置,因此使用一个idx变量记录当前路径中节点的个数。