import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
*
* Source : https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
*
*
* Given preorder and inorder traversal of a tree, construct the binary tree.
*
* Note:
* You may assume that duplicates do not exist in the tree.
*/
public class ConstructFromPreorderAndInorder {
/**
* 使用前序和中序遍历结果来恢复一颗二叉树
* preorder:root/left/right
* inorder:left/root/right
*
* 根据preorder找到root，然后根据inorder找到left，right
*
* @param preorderArr
* @param inorderArr
* @return
*/
public TreeNode build (char[] preorderArr, char[] inorderArr) {
return buildByRecursion(preorderArr, 0, preorderArr.length-1, inorderArr, 0, inorderArr.length-1);
}
public TreeNode buildByRecursion (char[] preorerArr, int preStart, int preEnd, char[] inorderArr, int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorerArr[preStart] - '0');
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (preorerArr[preStart] == inorderArr[i]) {
rootIndex = i;
break;
}
}
if (rootIndex < 0) {
return null;
}
int leftTreeSize = rootIndex - inStart;
int rightTreeSize = inEnd - rootIndex;
root.leftChild = buildByRecursion(preorerArr, preStart+1, preStart + leftTreeSize,
inorderArr, inStart, rootIndex-1);
root.rightChild = buildByRecursion(preorerArr,preEnd-rightTreeSize+1, preEnd,
inorderArr, rootIndex+1, inEnd );
return root;
}
/**
* 使用广度优先遍历将数转化为数组
*
* @param root
* @param chs
*/
public void binarySearchTreeToArray (TreeNode root, List<Character> chs) {
if (root == null) {
chs.add('#');
return;
}
List<TreeNode> list = new ArrayList<TreeNode>();
int head = 0;
int tail = 0;
list.add(root);
chs.add((char) (root.value + '0'));
tail ++;
TreeNode temp = null;
while (head < tail) {
temp = list.get(head);
if (temp.leftChild != null) {
list.add(temp.leftChild);
chs.add((char) (temp.leftChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
if (temp.rightChild != null) {
list.add(temp.rightChild);
chs.add((char)(temp.rightChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
head ++;
}
//去除最后不必要的
for (int i = chs.size()-1; i > 0; i--) {
if (chs.get(i) != '#') {
break;
}
chs.remove(i);
}
}
private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value;
public TreeNode(int value) {
this.value = value;
}
public TreeNode() {
}
}
public static void main(String[] args) {
/*
* 3
* / \
* 9 2
* / \
* 1 7
*/
char[] preorderArr = new char[]{'3','9','2','1','7'};
char[] inorderArr = new char[] {'9','3','1','2','7'};
ConstructFromPreorderAndInorder constructFromPreorderAndInorder = new ConstructFromPreorderAndInorder();
TreeNode root = constructFromPreorderAndInorder.build(preorderArr, inorderArr);
List<Character> chs = new ArrayList<Character>();
constructFromPreorderAndInorder.binarySearchTreeToArray(root, chs);
System.out.println(Arrays.toString(chs.toArray(new Character[chs.size()])));
}
}