PAT 1086: Tree Traversals Again [Java 실현] - 개선 판

이전 해법 은 앞 순서 와 중간 순 서 를 옮 겨 다 니 며 이 진 트 리 를 만 든 다음 출력 후 순 서 를 옮 겨 다 니 는 것 입 니 다.
나중에 진 월 선생님 의 설명 을 통 해 알 게 되 었 습 니 다. 사실은 이 진 트 리 를 만 들 필요 가 없습니다. 앞 순서 와 중 서 를 알 고 있 는 상황 에서 재 귀 를 이용 하여 후속 적 인 역 사 를 구 할 수 있 습 니 다.
자바 코드 는 다음 과 같 습 니 다:
import java.util.Scanner;
import java.util.Stack;

/**
 * Tree Traversals Again           ,              
 *                     ,              
 * 
 * @author Jacob
 *
 */

public class TreeTraversalsAgain {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int NODE_NUM = sc.nextInt();
		int[] preOrder = new int[NODE_NUM];
		int[] inOrder = new int[NODE_NUM];
		int preCount = 0;
		int inCount = 0;
		Stack stack = new Stack();
		int tmp;
		String operate;//     push  pop

		//                    
		//   :        “==”,  equals()
		for (int i = 0; i < NODE_NUM * 2; i++) {
			operate = sc.next();
			if (operate.equals("Push")) {
				tmp = sc.nextInt();
				stack.push(tmp);
				preOrder[preCount] = tmp;
				preCount++;
			} else if (operate.equals("Pop")) {
				inOrder[inCount] = stack.pop();
				inCount++;
			}
		}
		//
		int[] postOrder = new int[NODE_NUM];
		solve(preOrder, inOrder, postOrder, 0, 0, 0, NODE_NUM);

		for (int i = 0; i < NODE_NUM; i++) {
			System.out.print(postOrder[i]);
			if(i!=NODE_NUM-1){
				System.out.print(" ");
			}
		}

		sc.close();
	}

	public static void solve(int[] preOrder, int[] inOrder, int[] postOrder, int preLeft, int inLeft, int postLeft,
			int num) {
		if (num == 0) {
		}
		if (num == 1)
			postOrder[postLeft] = preOrder[preLeft];
		if (num > 1) {
			int findNum = 0; //          
			for (int i = inLeft; i < inLeft + num; i++) {
				if (preOrder[preLeft] == inOrder[i]) {
					findNum = i;
					break;
				}
			}
			postOrder[postLeft + num - 1] = preOrder[preLeft];
			int leftNum = findNum - inLeft;
			int rightNum = num - leftNum - 1;
			solve(preOrder, inOrder, postOrder, preLeft + 1, inLeft, postLeft, leftNum);
			solve(preOrder, inOrder, postOrder, preLeft + leftNum + 1, inLeft + leftNum + 1, postLeft + leftNum,
					rightNum);
		}
	}
}

/**
 *     
 * 
 */
class Node {
	int value;
	Node left;
	Node right;

	Node(int value) {
		this.value = value;
		left = null;
		right = null;
	}
}

좋은 웹페이지 즐겨찾기