剑指offer重建二叉树
今日的第二道菜,最一开始做剑指时,先找数组、字符串这些我熟悉的,无论难度,看到有关数据结构相关的题目直接跳动,今日一做,起码简单的还是能做出来的,哈哈不错不错~~~上菜:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
分析:是已知二叉树的前序遍历和中序遍历求二叉树啥样?我相信上过数据结构课的娃娃们一定会这个,首先明确一下前序遍历、中序遍历和后序遍历:
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
可以看这个链接,解释的还比较清楚。
https://www.cnblogs.com/bigsai/p/11393609.html
步骤:
1、前序遍历的第一个一定是根节点;
2、中序遍历中找到根节点位置,一分为二,左子树left和右子树right。
3、根据根节点在中序中的位置,将前序遍历中分为左右子树;
4、后面就是重复上面的步骤,知道找到叶子节点。
所以这个方法使用了递归。
上代码:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0)return null;
TreeNode tree = new TreeNode(pre[0]);
for(int i=0;i<in.length;i++){
if(in[i]==pre[0]){
tree.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i)); //从前序遍历和中序遍历中找到左子树
tree.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length)); //从前序遍历和中序遍历中找到右子树;
break; //找到了就直接跳出循环;
}
}
return tree;
}
}
牛客运行通过
运行时间:240ms
运行内存:22852Kb
这个运行好慢,占的内存也好大。
欢迎各位兄弟姐妹们交流哦~~