如何删除具有单个子节点的树节点的子节点

Question

我有一个用于树预序遍历的数组(节点值是深度值(。我想做的是通过删除只有一个子节点的内部节点的子节点来最小化树。

例如(最大深度 = 3 的树(问题在这里

可视化输入数组： [0， 1， 2， 3， 3， 1， 2， 3]
输出数组： [0， 1， 2， 2， 1]

算法应该如何？

Answer 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，然后递归调用该函数。如果有两个或更多这样的元素，请打印output_level，将output_level增加 1，并将函数递归应用于子元素划定的每个区间。执行递归调用时始终增加input_level。

对于示例输入A=[0, 1, 2, 3, 3, 1, 2, 3]，首先算法将找到值为 1 的元素，位于索引 1 和 5。然后它将打印 0，将 output_level 和 current_level 增加 1，并以递归方式调用自己两次：在范围 [1， 4] 和 [5， 7] 上。

在最坏的情况下，其复杂性为 O(n²((对于实际上是一个列表的退化树(，但平均为 O(nlog(n((，因为随机 n 元树的高度为 O(log(n((。

Answer 2

以下算法在 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 << ' ';
  }
}