[알고리즘] 백준 1991. 트리순회

 

 

 

 

 

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

1991번: 트리 순회

 

📌 내 풀이

import java.util.Arrays;
import java.util.Optional;
import java.util.Scanner;
import java.util.stream.Stream;

public class Prac {
	
	
	static StringBuilder sb;
	
	static String[] sArr;
	
	static int idx= 3;

	static Node[] nodeArr;
	
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      int T = Integer.parseInt(sc.nextLine());
      
      sb = new StringBuilder(T);
      
      nodeArr = new Node[T+1];
      
      sArr = sc.nextLine().split(" ");
      
      Arrays.fill(nodeArr, new Node(""));
      
      Node root = new Node(sArr[0]);
      
      nodeArr[0] = root;
      
      if(!".".equals(sArr[1])) {
    	  nodeArr[1] = root.lt = new Node(sArr[1]);
      }
      
      if(!".".equals(sArr[2])) {
    	  nodeArr[2] = root.rt = new Node(sArr[2]);
      }

     
      for(int i=0; i<T-1; i++) {

    	  sArr = sc.nextLine().split(" ");
    	   
    	  Optional<Node> rootNode = checkSameAndReturnOptiNode(sArr[0]);
    	  
    	  if(!".".equals(sArr[1])) {
    		  Optional<Node> leftNode = checkSameAndReturnOptiNode(sArr[1]);
    		  rootNode.get().lt = leftNode.get();
    	  }
    	  
    	  if(!".".equals(sArr[2])) {
    		  Optional<Node> rightNode = checkSameAndReturnOptiNode(sArr[2]);
    		  rootNode.get().rt = rightNode.get();
    	  }
      }
      
      preOrder(root);
      System.out.println(sb.toString());

      sb.setLength(0);
      inOrder(root);
      System.out.println(sb.toString());
      
      
      sb.setLength(0);
      postOrder(root);
      System.out.println(sb.toString());
      
   }
   
   static class Node{
	   String data;
	   Node lt, rt;
	   
	   Node(String data) {
		   this.data = data;
	   }
	   
	   public String toString() {
		   return data;
	   }
	   
   }
   
   static void preOrder(Node root) {
	   if(root == null) {
		   return;
	   }
	   sb.append(root.data);
	   preOrder(root.lt);
	   preOrder(root.rt);
	   
   }
   
   static void inOrder(Node root) {
	   if(root == null) {
		   return;
	   }
	   
	   inOrder(root.lt);
	   sb.append(root.data);
	   inOrder(root.rt);
	   
   }
   
   static void postOrder(Node root) {
	   if(root == null) {
		   return;
	   }
	   
	   postOrder(root.lt);
	   postOrder(root.rt);
	   sb.append(root.data);
   }
   
   static Optional<Node> checkSameAndReturnOptiNode(String s) {
	   
	   if(Stream.of(nodeArr).filter(x -> s.equals(x.data)).count()==0) {
 		  nodeArr[idx++] = new Node(s);
 	  }
	   
	   Optional<Node> rootNode = Stream.of(nodeArr)
 			  .filter(x -> s.equals(x.data))
 			  .reduce((a, b) -> a);
	   
	   return rootNode;
   }
   
   
}

 

 

 

📌 참고할만한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BJ_1991 {
   static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   static StringBuilder sb = new StringBuilder();
   static Node[] nodes;

   public static void main(String[] args) throws NumberFormatException, IOException {
      
      int N = Integer.parseInt(br.readLine());
      nodes=new Node[N+1];
      for(int i=1;i<=N;i++) {
         nodes[i]=new Node((char)(i+64));
      }
      for(int i=1;i<=N;i++) {
         String[] s=br.readLine().split(" ");
         char idx = s[0].charAt(0);
         char l = s[1].charAt(0);
         char r = s[2].charAt(0);
         if(l!='.') nodes[idx-'A'+1].Left=nodes[l-'A'+1];
         if(r!='.') nodes[idx-'A'+1].Right=nodes[r-'A'+1];
      }
      
      preorder(nodes[1]);
      sb.append("\n");
      inorder(nodes[1]);
      sb.append("\n");
      postorder(nodes[1]);
      sb.append("\n");
      
      System.out.print(sb.toString());
      
   }
   static class Node{
      char data;
      Node Left;
      Node Right;
      public Node(char data) {
         super();
         this.data = data;
      }
   }
   
   public static void preorder(Node node) {
      sb.append(node.data);
      if(node.Left!=null) preorder(node.Left);
      if(node.Right!=null) preorder(node.Right);
   }
   public static void inorder(Node node) {
      if(node.Left!=null) inorder(node.Left);
      sb.append(node.data);
      if(node.Right!=null) inorder(node.Right);
   }
   public static void postorder(Node node) {
      if(node.Left!=null) postorder(node.Left);
      if(node.Right!=null) postorder(node.Right);
      sb.append(node.data);
   }
   
}