'검지 Offer'2판의 재건 두 갈래 나무(5)

카탈로그

제목

사고방식

단계

코드

제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 역행 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8}와 중간 순서 역행 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6}를 입력하면 그림 2.6과 같은 두 갈래 트리를 재구성하고 머리 노드를 출력합니다.두 갈래 트리 노드의 정의는 다음과 같습니다.

stuct BinaryTreeNode {
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_right;
}

사고방식: 두 갈래 나무의 앞 순서를 훑어보는 서열에서 첫 번째 숫자는 항상 나무의 뿌리 노드의 값이다.그러나 중차 역행 시퀀스에서 루트 노드의 값은 시퀀스 중간에 있고 왼쪽 트리의 노드의 값은 루트 노드의 값 왼쪽에 있고 오른쪽 트리의 노드의 값은 루트 노드의 값 오른쪽에 있습니다.따라서 루트 노드의 값을 찾을 수 있도록 스캔 중인 순서가 필요합니다.
단계: 1.첫 번째 숫자 1은 루트 노드의 값입니다.스캔 중 시퀀스를 반복하면 루트 노드의 값 위치를 확인할 수 있습니다.중서 역행의 특징에 따라 뿌리 노드의 값 1 앞에 있는 세 개의 숫자는 모두 왼쪽 트리의 값이고 1 뒤에 있는 숫자는 모두 오른쪽 트리 노드의 값이다.
2. 중차순 반복 시퀀스에서 3개의 숫자가 왼쪽 트리 노드의 값이기 때문에 왼쪽 트리는 모두 3개의 왼쪽 트리 노드가 있다.마찬가지로 앞의 순서를 훑어보는 서열에서 뿌리 노드 뒤에 있는 3개의 숫자는 3개의 왼쪽 트리 노드의 값이고 뒤의 모든 숫자는 오른쪽 트리 노드의 값이다.이렇게 하면 우리는 앞의 순서와 중간의 순서 두 서열에서 각각 왼쪽, 오른쪽 트리에 대응하는 하위 서열을 찾을 수 있다.
3. 우리가 왼쪽, 오른쪽 트리의 전차 역행 서열과 중차 역행 서열을 각각 찾았기 때문에 우리는 같은 방법으로 왼쪽, 오른쪽 트리를 각각 구축할 수 있다.다음 일은 귀속적인 방법으로 끝낼 수 있다는 얘기다.
코드:

package test;

public class BinaryTreeNode {

	public static void main(String[] args) {
		int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
		int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
		TreeNode root = reConstructBinaryTree(pre, in);
		printTree(root);
	}
	
	private static void printTree(TreeNode root) {
		if(root != null) {
			printTree(root.left);
			System.out.println(root.value);
			printTree(root.right);
		}
	}
	
	public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		// 
		if(pre == null || in == null || pre.length != in.length)
			return null;
		return construct(pre, 0, pre.length - 1, in, 0, in.length - 1);
	}
	
	private static TreeNode construct(int[] pre, int ps, int pe, int[] in, int is, int ie) {
		//5. 
		if(ps > pe)
			return null;
		//1. 
		int root = pre[ps];
		
		//2. ， 
		int index = is;
		while(index <= ie && root != in[index])
			index++;
		
		//3. 
		TreeNode node = new TreeNode(root);
		
		//4. 
		node.left = construct(pre, ps + 1, ps + index - is, in, is, index - 1);
		node.right = construct(pre, ps + index - is + 1, pe, in, index + 1, ie);
		
		return node;
	}
	
	static class TreeNode {
		int value;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(int value) {
			this.value = value;
		}
	}
}