You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
112 lines
2.6 KiB
C++
112 lines
2.6 KiB
C++
/* Common leetcode.com problem's scaffold code
|
|
*/
|
|
#ifndef RADII_LEETCODE
|
|
#define RADII_LEETCODE
|
|
|
|
#include <iostream>
|
|
#include <limits>
|
|
#include <queue>
|
|
#include <string>
|
|
#include <typeinfo>
|
|
#include <vector>
|
|
|
|
/* Below TreeNode definition is copied from the problem at
|
|
https://leetcode.com/problems/path-sum-iii/ */
|
|
struct TreeNode {
|
|
int val;
|
|
TreeNode *left;
|
|
TreeNode *right;
|
|
TreeNode() : val(0), left(nullptr), right(nullptr) {}
|
|
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
|
|
TreeNode(int x, TreeNode *left, TreeNode *right)
|
|
: val(x), left(left), right(right) {}
|
|
};
|
|
/* Above TreeNode definition is copied from the problem at
|
|
https://leetcode.com/problems/path-sum-iii/ */
|
|
|
|
//
|
|
struct node_and_explored {
|
|
TreeNode *node;
|
|
bool explored;
|
|
};
|
|
|
|
std::ostream &operator<<(std::ostream &out, TreeNode *node) {
|
|
out << "{";
|
|
if (!node) {
|
|
out << "}";
|
|
return out;
|
|
}
|
|
|
|
std::queue<TreeNode *> bfs;
|
|
bfs.push(node);
|
|
while (bfs.size()) {
|
|
node = bfs.front();
|
|
bfs.pop();
|
|
if (node) {
|
|
out << node->val << ", ";
|
|
bfs.push(node->left);
|
|
bfs.push(node->right);
|
|
} else
|
|
out << "null, ";
|
|
}
|
|
out << "\b\b}";
|
|
return out;
|
|
}
|
|
|
|
template <typename T = int>
|
|
std::ostream &operator<<(std::ostream &out, const std::vector<T> &vec) {
|
|
out << "{";
|
|
if (!vec.size()) {
|
|
out << "}";
|
|
return out;
|
|
}
|
|
for (T e : vec) {
|
|
std::cout << e << ", ";
|
|
}
|
|
if (typeid(vec[0]) == typeid(std::string))
|
|
out << '\b';
|
|
out << " \b\b}";
|
|
return out;
|
|
}
|
|
|
|
template <typename T = int>
|
|
std::ostream &operator<<(std::ostream &out,
|
|
const std::vector<std::vector<T>> &vec_2d) {
|
|
out << "{";
|
|
if (!vec_2d.size()) {
|
|
out << "}";
|
|
return out;
|
|
}
|
|
for (const std::vector<T> &vec : vec_2d)
|
|
out << vec << ", ";
|
|
out << " \b\b}";
|
|
return out;
|
|
}
|
|
|
|
template <typename T = int> TreeNode *vector_to_tree(std::vector<T> &&vec) {
|
|
if (!vec.size())
|
|
return nullptr;
|
|
|
|
std::vector<TreeNode *> *nodes = new std::vector<TreeNode *>;
|
|
for (std::size_t i = 0, upto = vec.size(); i < upto; i++) {
|
|
// NOTE: cannot use T_MAX in problem input since treating it as empty node
|
|
if (vec[i] == std::numeric_limits<T>::max())
|
|
nodes->emplace_back(nullptr);
|
|
else
|
|
nodes->emplace_back(new TreeNode(vec[i]));
|
|
}
|
|
|
|
for (std::size_t i = 0, upto = vec.size(); i < upto; i++) {
|
|
if (!(*nodes)[i])
|
|
continue;
|
|
std::size_t left = 2 * i + 1, right = 2 * i + 2;
|
|
if (left < upto)
|
|
(*nodes)[i]->left = (*nodes)[left];
|
|
if (right < upto)
|
|
(*nodes)[i]->right = (*nodes)[right];
|
|
}
|
|
|
|
return (*nodes)[0];
|
|
}
|
|
|
|
#endif |