上牛客网做了一道剑指offer的算法题 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
看了别人的代码，感觉自己真的 ...
贴下自己吧，毕竟花了很长时间解决的
public class Solution {
private static int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
private static int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return buildChildTree(null, pre, in);
}
// 寻找根节点值
public static int searchRootValue(int[] pre) {
int root;
if (pre.length == 0) {
return 0;
}
root = pre[0];
return root;
}
// 寻找根节点下标
public static int searchRootIndex(int[] pre, int[] in) {
if (pre == null && in == null
|| pre.length == 0 && in.length == 0) {
return -1;
}
// 只有一个节点，根下标就是 0
if (pre.length == 1 && in.length == 1)
return 0;
int rootValue = searchRootValue(pre);
int index = 0; // 用来标记根节点下标
for (int i = 0; i < in.length; i++) {
if (in[i] == rootValue) {
index = i;
}
}
return index;
}
// 寻找左子树中序数组
public static int[] searchLeftChildInArrays(int[] pre, int[] in) {
if (pre == null && in == null
// 只有一个节点则无法找到其子树
|| pre.length <= 1 && in.length <= 1) {
return null;
}
int rootIndex = searchRootIndex(pre, in);
int[] result = new int[rootIndex];
for (int i = 0; i < rootIndex; i++) {
result[i] = in[i];
}
return result;
}
// 寻找右子树中序数组
public static int[] searchRightChildInArrays(int[] pre, int[] in) {
if (pre == null || in == null
// 只有一个节点则无法找到其子树
|| pre.length <= 1 || in.length <= 1) {
return null;
}
int rootIndex = searchRootIndex(pre, in);
int[] result = new int[in.length - rootIndex - 1];
for (int i = 0; i < (in.length - rootIndex - 1); i++) {
result[i] = in[rootIndex + 1 + i];
}
return result;
}
// 寻找前序根节点的值
public static int searchPreLeftChildRootValue(int[] pre, int[] in) {
int[] leftArrays = searchLeftChildInArrays(pre, in);
int rootValue = 0;
for (int i = 0; i < pre.length; i++) {
for (int j = 0; j < leftArrays.length; j++) {
if (leftArrays[j] == pre[i]) {
rootValue = leftArrays[j];
return rootValue;
}
}
}
return rootValue;
}
// 寻找左子树前序数组
public static int[] searchLeftChildPreArrays(int[] pre, int[] in) {
if (pre == null || in == null ||
pre.length <= 1 || in.length <= 1) {
return null;
}
int length = searchLeftChildInArrays(pre, in).length;
int[] result = new int[length];
for (int i = 0; i < result.length; i++) {
result[i] = pre[i + 1];
}
return result;
}
// 寻找右子树前序数组
public static int[] searchRightChildPreArrays(int[] pre, int[] in) {
if (pre == null || in == null ||
pre.length <= 1 || in.length <= 1) {
return null;
}
int rightLength = searchRightChildInArrays(pre, in).length;
int[] result = new int[rightLength];
for (int i = 0; i < result.length; i++) {
result[i] = pre[pre.length - rightLength + i];
}
return result;
}
// 递归构建一颗树，返回根节点
public static TreeNode buildChildTree(TreeNode father, int[] pre, int[] in) {
if (pre == null && in == null || pre.length == 0 && pre.length == 0) {
return father;
}
int rootValue = searchRootValue(pre);
father = new TreeNode(rootValue);
int[] leftChildPreArrays = searchLeftChildPreArrays(pre, in);
int[] leftChildInArrays = searchLeftChildInArrays(pre, in);
int[] rightChildPreArrays = searchRightChildPreArrays(pre, in);
int[] rightChildInArrays = searchRightChildInArrays(pre, in);
if (leftChildPreArrays != null && leftChildPreArrays.length != 0) {
// printAll(leftChildPreArrays, leftChildInArrays);
TreeNode leftNode = buildChildTree(father, leftChildPreArrays, leftChildInArrays);
father.left = leftNode;
}
if (rightChildPreArrays != null && rightChildPreArrays.length != 0) {
// printAll(rightChildPreArrays, rightChildInArrays);
TreeNode rightNode = buildChildTree(father, rightChildPreArrays, rightChildInArrays);
father.right = rightNode;
}
return father;
}
public static void main(String[] args) {
TreeNode root = new Solution().reConstructBinaryTree(pre, in);
}
public static void printAll(int[] pre, int[] in) {
int index = searchRootValue(pre);
System.out.print("中序根节点值\t");
System.out.println(index);
System.out.print("左子树中序数组\t");
int[] leftChildInArrays = searchLeftChildInArrays(pre, in);
if (leftChildInArrays != null)
for (int child : leftChildInArrays) {
System.out.print(child + " ");
}
System.out.println();
System.out.print("右子树中序数组\t");
int[] rightChildInArrays = searchRightChildInArrays(pre, in);
if (rightChildInArrays != null)
for (int child : rightChildInArrays) {
System.out.print(child + " ");
}
System.out.println();
System.out.print("左子树前序数组\t");
int[] leftChildPreArrays = searchLeftChildPreArrays(pre, in);
if (leftChildPreArrays != null)
for (int child : leftChildPreArrays) {
System.out.print(child + " ");
}
System.out.println();
System.out.print("右子树前序数组\t");
int[] rightChildPreArrays = searchRightChildPreArrays(pre, in);
if (rightChildPreArrays != null)
for (int child : rightChildPreArrays) {
System.out.print(child + " ");
}
System.out.println("\n\n");
}
public static void printTree(TreeNode treeNode) {
if (treeNode == null) {
System.out.println("到结尾了");
}
System.out.println(treeNode.val);
if (treeNode.left != null) {
printTree(treeNode.left);
System.out.println("输出结束");
}
if (treeNode.right != null) {
printTree(treeNode.right);
System.out.println("输出结束");
}
}
}
网友评论