剑指 offer || 重建二叉树
题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
解题思路:
(1)明白什么是前序遍历和中序遍历
前序遍历:根--左--右
中序遍历:左--中--右
(2)知道前序遍历和中序遍历怎么确定一颗二叉树
1)确定根结点,在前序遍历中第一个节点即为根结点root。
2)根据第一步确定的根结点,在中序中找到根结点root所在的位置,root的左侧即为左节点leftNode、右侧即为右节点rightNode。
3)分别对第二步确定的左节点和右节点一次进行前两步的操作,直到遍历到左右节点的叶子结点为止。
代码实现:
public static TreeNodee reConstructBinaryTree(int[] pre, int[] middle){
TreeNodee root = new TreeNodee(pre[0]);
int length = pre.length;
//只有一个元素
if(length == 0) {
root.left = null;
root.right = null;
return root;
}
//中序中确定根元素
int i;
int rootval = root.val;
System.out.println(rootval);
for(i = 0; i < length; i++) {
if(rootval == middle[i]) {
break;
}
}
//构建左子树
if(i > 0) {
int[] press = new int[i];
int[] middless = new int[i];
for(int j = 0; j < i; j++) {
press[j] = pre[j+1];
}
for(int j = 0; j < i; j++) {
middless[j] = middle[j];
}
root.left = reConstructBinaryTree(press, middless);
}else {
root.left = null;
}
//构建右子树
if(length-i-1 > 0) {
int[] pres = new int[length-i-1];
int[] middles = new int[length-i-1];
for(int j = i+1; j<length; j++) {
pres[j-i-1] = pre[j];
middles[j-i-1] = middle[j];
}
root.right = reConstructBinaryTree(pres, middles);
}else {
root.right = null;
}
return root;
}