c++对于每棵二叉树,都输出值最小的路径上叶子节点的值。如果多条路径的值最小,则选择叶子节点值最小的路径。
时间: 2024-04-12 19:31:55 浏览: 88
你可以使用深度优先搜索(DFS)来解决这个问题。首先,你需要定义一个数据结构来表示二叉树的节点。每个节点应该包含一个值和指向左右子节点的指针。
然后,你可以使用递归函数来实现DFS。在递归函数中,你需要传递当前节点、当前路径的和以及当前路径上的最小叶子节点值。对于每个节点,你可以将其值加到当前路径的和中,并且更新当前路径上的最小叶子节点值。如果当前节点是叶子节点,则比较当前路径的和和最小路径的和,如果更小,则更新最小路径的和和最小路径。
以下是一个示例代码:
```cpp
#include <iostream>
#include <vector>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode* node, int sum, int& minSum, int& minLeaf, std::vector<int>& path) {
if (node == nullptr) {
return;
}
sum += node->val;
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) {
if (sum < minSum || (sum == minSum && node->val < minLeaf)) {
minSum = sum;
minLeaf = node->val;
}
}
dfs(node->left, sum, minSum, minLeaf, path);
dfs(node->right, sum, minSum, minLeaf, path);
path.pop_back();
}
std::vector<int> minPath(TreeNode* root) {
int minSum = INT_MAX;
int minLeaf = INT_MAX;
std::vector<int> path;
dfs(root, 0, minSum, minLeaf, path);
return path;
}
int main() {
// 构造二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 获取最小路径
std::vector<int> minPath = minPath(root);
// 输出结果
std::cout << "Minimum path: ";
for (int i : minPath) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
```
这段代码中,我们首先构造了一个示例二叉树。然后调用 `minPath` 函数来获取最小路径。最后,我们输出了最小路径的值。
注意,这只是一个简单的示例代码,你可以根据自己的需求进行修改和扩展。
阅读全文