视源
1、给定一个二叉树的根节点，返回中序遍历（不用递归）
#include <iostream>
#include <vector>
#include <stack>
// 定义二叉树的节点结构
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 中序遍历的迭代函数
std::vector<int> inorderTraversalIterative(TreeNode* root) {
std::vector<int> result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
while (current != nullptr) {
stack.push(current);
current = current->left;
}
current = stack.top();
stack.pop();
result.push_back(current->val);
current = current->right;
}
return result;
}
int main() {
// 构建一个简单的二叉树
// 1
// / \
// 2 3
// / \
// 4 5
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);
// 进行中序遍历
std::vector<int> result = inorderTraversalIterative(root);
for (int val : result) {
std::cout << val << " ";
}
return 0;
}
2、
#include <iostream>
#include <vector>
#include <stack>
// 定义二叉树的节点结构
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 中序遍历的迭代函数
std::vector<int> inorderTraversalIterative(TreeNode* root) {
std::vector<int> result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
while (current != nullptr) {
stack.push(current);
current = current->left;
}
current = stack.top();
stack.pop();
result.push_back(current->val);
current = current->right;
}
return result;
}
int main() {
// 构建一个简单的二叉树
// 1
// / \
// 2 3
// / \
// 4 5
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);
// 进行中序遍历
std::vector<int> result = inorderTraversalIterative(root);
for (int val : result) {
std::cout << val << " ";
}
return 0;
}
2、
#include <iostream>
#include <string>
#include <bitset>
std::string ipv4ToCharSequence(const std::string &ip, const std::string &charset) {
// 将IPv4地址分割成四个部分
std::string parts[4];
int partIndex = 0;
size_t prevPos = 0, pos = 0;
for (pos = 0; pos < ip.size(); ++pos) {
if (ip[pos] == '.') {
parts[partIndex] = ip.substr(prevPos, pos - prevPos);
++partIndex;
prevPos = pos + 1;
}
}
// 获取最后一个部分
parts[partIndex] = ip.substr(prevPos);
// 计算n的值
int n = static_cast<int>(std::log2(charset.size()));
std::string result;
// 遍历每个部分
for (const auto &part : parts) {
// 将每个部分转换为二进制字符串
std::bitset<32> binary(static_cast<unsigned int>(std::stoi(part)));
std::string binaryStr = binary.to_string();
// 补齐高位0，使得总位数为n的整数倍
int padding = n - (binaryStr.size() % n);
if (padding == n) padding = 0; // 如果已经能被n整除，则不需要补0
binaryStr = std::string(padding, '0') + binaryStr;
// 将二进制字符串映射到字符集
for (size_t i = 0; i < binaryStr.size(); i += n) {
std::string bitGroup = binaryStr.substr(i, n);
int index = std::stoi(bitGroup, nullptr, 2);
result += charset[index];
}
}
return result;
}
int main() {
std::string ipv4 = "192.168.1.1";
std::string charset = "01";
std::cout << ipv4ToCharSequence(ipv4, charset) << std::endl;
return 0;
}
