[UVa] 548 - Tree

題目

Link: UVa 548 - Tree

Hint

下面兩行分別是 inorder 和 postorder 的 traversal

3 2 1 4 5 7 6
3 1 2 5 6 7 4

postorder 最後一個一定是 root
inorder 中, root 左邊是左子樹,右邊是右子樹

3 2 1  [4]  5 7 6
3 1 2  5 6 7  [4]

Code

C++

#include <string>
#include <sstream>
#include <iostream>
#include <vector>

// less stack consumption recursion
static std::vector<int> in_order, post_order;
static int min, min_node;

struct Node
{
    int data;
    Node* left;
    Node* right;
    explicit Node(int data) : data(data), left(), right() {};
    ~Node() { delete left, right; }
};

Node* build_tree(int in_order_start, int in_order_end, int post_order_start, int post_order_end);
void dfs_min(Node* root, int parent);

int main()
{
  std::string line;
  std::stringstream buf;
  Node* root;
  int temp, length;

  std::ios::sync_with_stdio(false);

  while (std::getline(std::cin, line))
  {
    buf.clear();
    buf << line;

    in_order.clear();
    while (buf >> temp) in_order.push_back(temp);

    std::getline(std::cin, line);
    buf.clear();
    buf << line;

    post_order.clear();
    while (buf >> temp) post_order.push_back(temp);

    length = static_cast<int>(post_order.size());
    root = build_tree(0, length, 0, length);

    min = 0x7fffffff;
    dfs_min(root, 0);

    std::cout << min_node << std::endl;
    delete root;
  }

  return 0;
}

Node* build_tree(int in_order_start, int in_order_end, int post_order_start, int post_order_end)
{
  if (in_order_start >= in_order_end or post_order_start >= post_order_end) return nullptr;
  int root_position, root_data = post_order[post_order_end - 1];
  auto* root = new Node(root_data);

  for (root_position = in_order_start; root_position < in_order_end; ++root_position)
    if (in_order[root_position] == root_data) break;

  root->left = build_tree(in_order_start, root_position,
                          post_order_start, post_order_start + root_position - in_order_start);
  root->right = build_tree(root_position + 1, in_order_end,
                           post_order_start + root_position - in_order_start, post_order_end - 1);

  return root;
}

void dfs_min(Node* root, int parent)
{
  if (root == nullptr) return;
  if (root->left || root->right)
  {
    dfs_min(root->left, parent + root->data);
    dfs_min(root->right, parent + root->data);
  }
  else if (parent + root->data < min)
  {
    min = parent + root->data;
    min_node = root->data;
  }
}

Show Comments