二叉树还原

已经前序遍历  与 中序遍历 的 结果，还原出二叉树：

private static String[] pre = {"G", "D", "A", "F", "E", "M", "H", "Z"}; private static String[] in = {"A", "D", "E", "F", "G", "H", "M", "Z"}; private static String[] post = {"A", "E", "F", "D", "H", "Z", "M", "G"};

public static Node getRootPreIn(String[] pre, String[] in) { if (pre == null || in == null) { return null; } Node root = new Node(pre[0]); if (root == null) { return null; } int len = pre.length; if (len == 0) { return null; } if (len == 1) { root.left = null; root.right = null; return root; } int index = getIndex(in, root.valStr); if (index <= 0) { //中序遍历结果，根节点是第一个，则说明没有左子树 root.left = null; } else { String[] preChild = new String[index]; String[] inChild = new String[index]; System.arraycopy(pre, 1, preChild, 0, index); System.arraycopy(in, 0, inChild, 0, index); root.left = getRootPreIn(preChild, inChild); } if ((len - (index + 1)) <= 0) { //中序遍历结果，根节点是最后一个，则说明没有右子树 root.right = null; } else { //index+1 ---> 左子树与根节点加一起的长度 //len-(index+1) ---> 右子树的长度 String[] preChild = new String[len - (index + 1)]; String[] inChild = new String[len - (index + 1)]; System.arraycopy(pre, index + 1, preChild, 0, len - (index + 1)); System.arraycopy(in, index + 1, inChild, 0, len - (index + 1)); root.right = getRootPreIn(preChild, inChild); } return root; } public static int getIndex(String[] array, String element) { if (array == null || TextUtils.isEmpty(element)) { return -1; } for (int i = 0; i < array.length; i++) { if (element.equalsIgnoreCase(array[i])) { return i; } } return -1; }

public static class Node { int valInt = -1; String valStr; Node left; Node right; public Node(int self) { this.valInt = self; } public Node() { } public Node(String self) { this.valStr = self; } public String getValStr() { return valStr; } public void setValStr(String valStr) { this.valStr = valStr; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public int getValInt() { return valInt; } public void setValInt(int valInt) { this.valInt = valInt; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } }

public static void print(Node root) { System.out.println("printNodeValue=====pre====="); leftTraversal(root); System.out.println("printNodeValue======in===="); midTraversal(root); System.out.println("printNodeValue======post===="); rightTraversal(root); } public static Node getRoot() { Node root= getRootPreIn(pre, in); //return getRoot(pre, in); print(root); return root; }

1.前序遍历的第一个节点一定是二叉树根节点；

2.中序遍历的结果中，根节点左侧的数据一定是 根节点左子树相关数据，右侧一定是根节点右子树相关数据；

    private static String[] pre = {"G", "D", "A", "F", "E", "M", "H", "Z"};     private static String[] in = {"A", "D", "E", "F", "G", "H", "M", "Z"};

所以可以看出来，ADEF 是左子树上的数据，HMZ 是右子树上的数据；

G节点左孩子应该是D，以D为根节点的 前序遍历应该是 DAFE，中序遍历应该是 ADEF；

G节点右孩子应该是M，以M为根节点的 前序遍历赢还是 MHZ，中序遍历应该是HMZ；

然后递归。。。。。。