c++ - 二叉搜索树中最后 N 个节点的总和
问题描述
我想写一个函数,得到一个数 N 和一个二叉搜索树,然后这个函数需要对树的最后 N 个节点的值求和。节点的值从高到低。我不能使用辅助函数或静态变量。
例如,如果函数获得该二叉搜索树并且 N 的值为 3,则输出将为:7+6+5。如果 N 为 4,则为:7+6+5+3。
对算法有什么想法吗?
解决方案
您可以简单地以相反的顺序访问树,这意味着从根开始并做三件事:
- 访问右分支
- 访问自身节点,并在需要时累加总和
- 访问左分支
并在 k 项累积时停止迭代。
#include <iostream>
struct Node {
int value;
Node* left = nullptr;
Node* right = nullptr;
Node(int v) : value(v) {}
};
// Visit the tree in reverse order and get sum of top k items.
int sumK(Node* root, int& k) {
if (root == nullptr) return 0;
int sum = 0;
if (k > 0 && root->right) {
sum += sumK(root->right, k);
}
if (k > 0) {
sum += root->value;
k--;
}
if (k > 0 && root->left) {
sum += sumK(root->left, k);
}
return sum;
}
int main () {
// The following code hard coded a tree matches the picture in your question.
// I did not free the tree, so there will be memory leaking, but that is not relevant to this test.
Node* root = new Node(5);
root->right = new Node(6);
root->right->right = new Node(7);
root->left = new Node(3);
root->left->right = new Node(4);
root->left->left = new Node(2);
root->left->left->left = new Node(1);
// TODO: delete the tree after testing.
int k = 1;
std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
k = 3;
std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
k = 4;
std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
}
输出是:
k=1 sum=7
k=3 sum=18
k=4 sum=22
推荐阅读
- python - 如何覆盖枚举标志子类的迭代行为?
- python - tkinter doesn't work after building the app with cx_Freeze on python
- javascript - Waiting for variables to be defined?
- python - Loading Text Data from a CSV and Applying a Tokenizer in Keras
- flutter - Build multiple iOS / Android apps with one Flutter code-base?
- pandas - 根据条件对数据框应用过滤器
- c# - ASP.NET Core 3.1 and Entity Framework Core delete multiple records from database based on ID
- arrays - Iterate in array of type struct
- flutter - Radio app using flutter, audio stops after 3 mins when screen is off
- python - 如何让 Travis CI 在 python 中使用 input()?