검지offer 면접문제 5 - 끝에서 끝까지 인쇄 체인표/6 - 두 갈래 나무 재구성

제목 5:
단일 체인 테이블에 대해 이미 그의 머리 결점을 알고 있으며, 끝에서 끝까지 안의 내용을 인쇄할 것을 요구한다.
생각:
손에 머리가 있으니 끝에서 끝까지 인쇄하려면 먼저 창고가 생각난다.
창고를 생각하니 정말 실현해야 한다. 더욱 공교로운 방법이 하나 있다. 같은 창고--귀속이다.

public static void printLinkedListFromTail(Node node) {
		if (node != null) {
			printLinkedListFromTail(node.next);
			System.out.println(node);
		}
	}

	class Node {
		Node next;
		int value;

		@Override
		public String toString() {
			return "Node [value=" + value + "]";
		}
	}

제목 6:
어떤 두 갈래 나무의 앞차례 역주행과 중간차례 역주행 결과를 입력하십시오. 이 두 갈래 나무는 입력한 앞차례 역주행과 중간차례 역주행 결과에 중복된 숫자가 포함되지 않는다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8}와 중간 순서 반복 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6}를 입력하면 두 갈래 나무를 재건하고 그의 머리 결점을 출력합니다

class BinaryTreeNode{
	int value;
	BinaryTreeNode left;
	BinaryTreeNode right;
}

생각은 어떻게 하는가:
우선 앞의 순서가 두루 돌아다니는 것을 알아야 한다.
1. 그러면 앞의 첫 번째 숫자는 루트 노드가 틀림없다.
2. 이 뿌리 노드에 따라 중간 순서로 안쪽을 훑어보고 위치를 찾으면 이 노드 이전의 것은 모두 뿌리 왼쪽에 있고 그 다음은 모두 뿌리 오른쪽에 있다.
3. 그리고 작은 덩어리로 돌아가 각개 격파

class BinaryTreeNode {
		int value;
		BinaryTreeNode left;
		BinaryTreeNode right;

		@Override
		public String toString() {
			return "BinaryTreeNode [value=" + value + ", left=" + left
					+ ", right=" + right + "]";
		}

	}

	public BinaryTreeNode refactorTree(int[] first, int[] middle) {
		if (first == null || middle == null || first.length != middle.length) {
			throw new RuntimeException();
		}
		if (first.length == 0) {
			return null;
		}
		//  ， ， 
		int root = first[0];
		int rootIndex = 0;
		for (int i = 0; i < first.length; i++) {
			if (middle[i] == root) {
				rootIndex = i;
				break;
			}
		}
		BinaryTreeNode tree = new BinaryTreeNode();
		tree.value = root;

		//  ， ， 
		tree.left = refactorTree(Arrays.copyOfRange(first, 1, rootIndex + 1),
				Arrays.copyOfRange(middle, 0, rootIndex));
		//  ， 
		tree.right = refactorTree(
				Arrays.copyOfRange(first, rootIndex + 1, first.length),
				Arrays.copyOfRange(middle, rootIndex + 1, middle.length));

		return tree;
	}