我有一个用于树的前序遍历的数组(节点值是深度值)。我想做的就是通过删除只有一个孩子的内部节点的孩子来最小化树。
作为示例(最大深度 = 3 的树)
问题在此处可视化
输入数组:[0, 1, 2, 3, 3, 1, 2, 3]
输出数组: [0, 1, 2, 2, 1]
算法应该如何?
我有一个用于树的前序遍历的数组(节点值是深度值)。我想做的就是通过删除只有一个孩子的内部节点的孩子来最小化树。
作为示例(最大深度 = 3 的树)
问题在此处可视化
输入数组:[0, 1, 2, 3, 3, 1, 2, 3]
输出数组: [0, 1, 2, 2, 1]
算法应该如何?
一个简单的 O(nlog(n)) 平均情况算法源于通过分而治之的方法来解决问题。
input_level = 0
从, output_level=0
, left=0
,开始right=n-1
。
input_level+1
在每个递归步骤中,计算输入数组A
中值在 [ left
, right
]范围内的元素。这些是当前节点的子节点。如果没有这样的元素,打印output_level
并返回。如果只有一个这样的元素,“删除”当前节点(即不打印它),增加left
1,并递归调用函数。如果有两个或更多这样的元素,则 printoutput_level
增加output_level
1,并将函数递归地应用于由子元素划分的每个间隔。进行递归调用时始终增加。input_level
对于示例 input A=[0, 1, 2, 3, 3, 1, 2, 3]
,首先该算法将在索引 1 和 5 处找到值为 1 的元素。然后它会打印 0,增加1output_level
并current_level
递归调用自身两次:在范围 [1, 4] 和 [5, 7]。
其复杂性在最坏情况下为 O(n 2 )(对于实际上是列表的退化树),但平均为 O(nlog(n)),因为随机 n 元树的高度为 O(日志(n))。
以下算法在 O(N) 中运行。我想这次我猜对了。
#include <algorithm>
#include <iostream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
void mark_nodes(const std::vector<unsigned>& tree,
std::vector<bool>& mark) {
// {depth, index, mark?}
using triple = std::tuple<unsigned, unsigned, bool>;
std::stack<triple> stk;
stk.push({0, 0, false});
for (auto i = 1u; i < mark.size(); ++i) {
auto depth = tree[i];
auto top_depth = std::get<0>(stk.top());
if (depth == top_depth) {
stk.pop();
if (stk.size()) std::get<2>(stk.top()) = false;
continue;
}
if (depth > top_depth) {
std::get<2>(stk.top()) = true;
stk.push({depth, i, false});
continue;
}
while (std::get<0>(stk.top()) != depth) {
mark[std::get<1>(stk.top())] = std::get<2>(stk.top());
stk.pop();
}
mark[std::get<1>(stk.top())] = std::get<2>(stk.top());
stk.pop();
if (stk.size()) std::get<2>(stk.top()) = false;
stk.push({depth, i, false});
}
mark[0] = false;
}
std::vector<unsigned> trim_single_child_nodes(
std::vector<unsigned> tree) {
tree.push_back(0u);
std::vector<bool> mark(tree.size(), false);
mark_nodes(tree, mark);
std::vector<unsigned> ret(1, 0);
tree.pop_back();
mark.pop_back();
auto max_depth = *std::max_element(tree.begin(), tree.end());
std::vector<unsigned> depth_map(max_depth + 1, 0);
for (auto i = 1u; i < tree.size(); ++i) {
if (mark[i]) {
if (tree[i] > tree[i - 1]) {
depth_map[tree[i]] = depth_map[tree[i - 1]];
}
} else {
if (tree[i] > tree[i - 1]) {
depth_map[tree[i]] = depth_map[tree[i - 1]] + 1;
}
ret.push_back(depth_map[tree[i]]);
}
}
return ret;
}
int main() {
std::vector<unsigned> input = {0, 1, 2, 3, 3, 1, 2, 3};
auto output = trim_single_child_nodes(input);
for (auto depth : output) {
std::cout << depth << ' ';
}
}