[BOJ] 2263 - 트리의 순회

https://www.acmicpc.net/problem/2263

BOJ - 트리의 순회

문제 유형: 트리, dfs, 분할 정복

문제 난이도: Gold I

시간 제한: 5초

메모리 제한: 128MB

 

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

 

출력

첫째 줄에 프리오더를 출력한다.

 

풀이

중위순회의 정보는 노드들간의 좌우관계를 알려준다.

후위순회에서의 마지막원소는 항상 루트노드의 값이다.

즉, 루트노드를 중위순회에서의 위치를 이용해서, 왼쪽 서브트리와 오른쪽 서브트리를 추가로 분할할 수 있다.

[영역의 맨 왼쪽위치, 루트노드에서 중위순회에서의 위치-1]이 왼쪽 서브트리 영역이고,

[루트노드에서의 중위순회에서의 위치, 현재 루트 앞의 위치]까지가 오른쪽 서브트리이다.

이제, 분할 정복을 이용해서 트리를 복구하고, 복구된 트리를 전위순회 하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;
int inorder[100001], postorder[100001];
unordered_map<int, int> inorderIdx;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;

  TreeNode(int val) {
    this->val = val;
    this->left = nullptr;
    this->right = nullptr;
  }
};

void preOrder(TreeNode *root) {
  cout << root->val << " ";
  if (root->left)
    preOrder(root->left);
  if (root->right)
    preOrder(root->right);
}

TreeNode *buildTree(int inStart, int inEnd, int postStart, int postEnd) {
  if (inStart > inEnd || postStart > postEnd)
    return nullptr;

  int rootVal = postorder[postEnd];
  auto root = new TreeNode(rootVal);

  int rootIdx = inorderIdx[rootVal];

  int leftSize = rootIdx - inStart;

  root->left =
      buildTree(inStart, rootIdx - 1, postStart, postStart + leftSize - 1);
  root->right =
      buildTree(rootIdx + 1, inEnd, postStart + leftSize, postEnd - 1);

  return root;
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  for (int i = 0; i < n; ++i) {
    cin >> inorder[i];
    inorderIdx[inorder[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    cin >> postorder[i];
  }

  auto root = buildTree(0, n - 1, 0, n - 1);

  preOrder(root);
  cout << "\n";

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

type TreeNode struct {
	val   int32
	left  *TreeNode
	right *TreeNode
}

var n int32
var inorder []int32
var postorder []int32
var inorderIdx map[int32]int32
var reader *bufio.Reader
var writer *bufio.Writer

func preorder(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Fprintf(writer, "%d ", root.val)
	preorder(root.left)
	preorder(root.right)
}

func buildTree(inStart, inEnd, postStart, postEnd int32) *TreeNode {
	if inStart > inEnd || postStart > postEnd {
		return nil
	}

	rootVal := postorder[postEnd]
	root := &TreeNode{val: rootVal}
	rootIdx := inorderIdx[rootVal]
	leftSize := rootIdx - inStart

	root.left = buildTree(inStart, rootIdx-1, postStart, postStart+leftSize-1)
	root.right = buildTree(rootIdx+1, inEnd, postStart+leftSize, postEnd-1)

	return root
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	fmt.Fscan(reader, &n)
	inorder = make([]int32, n)
	postorder = make([]int32, n)
	inorderIdx = make(map[int32]int32)

	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &inorder[i])
		inorderIdx[inorder[i]] = i
	}

	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &postorder[i])
	}

	root := buildTree(0, n-1, 0, n-1)
	preorder(root)
	fmt.Fprintln(writer)

}