题目概述(中等难度)
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
题目链接:
点我进入leetcode
思路与代码
思路展现
这道题目的思路是这样的:
1:首先通过前序遍历找到我们的根
2:在中序遍历中找到根的位置,此时根的左边是左树,根的右边是右树
下面来看整体细节思路:
1:首先我们定义一个i指向我们前序遍历结果数组的第一个元素,也就是指向我们的A,那么A此时就是我们二叉树的根节点,并且我们根据中序遍历的结果可以分析出这棵二叉树的左边包含了D,B,G,E四个节点,根的右树包含了C,H,F三个节点.示意图如下所示:
2:找到二叉树的根节点之后,i开始向后遍历,遍历到了我们的B,此时在中序遍历中我们只需要在DBGE这个左区间去找B即可,没有必要在整个中序遍历的数组中再去寻找B,然后构建我们的二叉树,可以看到我们寻找元素的时候是在一个范围内去寻找这个元素的,所以我们需要定义一个inbegin和inend下标来指向我们数组范围的头和尾,这两个下标代表我们寻找元素时所在的区间的头和尾,一开始这个inbegin和inend下标分别指向我们中序遍历结果的头和尾,后面这两个下标会随着中序遍历结果的拆分而发生位置的变化:
如下是一开始两个下标所在的位置:
当找到A这个根节点之后,此时分成了两个区间分别作为A的左子树区间和A的右子树区间,B在左区间内,所以inbegin和inend这两个下标分别指向左区间的头和尾.
此时再把二叉树进行划分:
3:此时i继续向下遍历到了我们的D,D在我们刚才所划分区域的左边,所以此时inbegin和inend都同时指向了我们的D
我们会发现inbegin和我们的inend已经相遇了,当有一天inbegin走到了inend的后面就说明我们这棵树已经递归完了,而这个条件也是我们程序递归的终止条件
大致来说思路就是上面这样一个思路:现在我们来进行代码的实现:
代码示例
首先我们写出第一版代码:
class Solution { public TreeNode buildTreeChild(int[] preorder,int preIndex,int[] inorder,int inbegin,int inend) { //递归的终止条件 if(inbegin > inend) { return null; } //创建根节点 TreeNode root = new TreeNode(preorder[preIndex]); int index = findValInorder(inorder,preorder[preIndex],inbegin,inend); preIndex++; root.left = buildTreeChild(preorder,preIndex,inorder,inbegin,index - 1); root.right = buildTreeChild(preorder,preIndex,inorder,index + 1,inend); return root; } //寻找中序遍历后的结果 public int findValInorder(int[] inorder,int key,int inbegin,int inend) { for(int i = inbegin;i <= inend;i++) { if(inorder[i] == key) { return i; } } return -1; } public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null) { return null; } if(preorder.length == 0 || inorder.length == 0) { return null; } //用于遍历前序遍历的结果 int preIndex = 0; return buildTreeChild(preorder,0,inorder,0,inorder.length - 1); } }
但是我们会发现此时leetcode会报数组越界错误:
原因是我们用于遍历前序遍历结果的preIndex没有定义成全局变量,每次我们执行完buildTreeChild(preorder,preIndex,inorder,inbegin,index - 1);这条语句后,preIndex又回到了递归前的值,并没有到它该到的位置,所以我们应该把preIndex定义成全局变量.
正确代码如下:
class Solution { //preIndex为前序遍历的下标,用于遍历前序遍历的结果 public int preIndex = 0; public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) { //说明没有左树或者没有有树,递归的终止条件 if(inbegin > inend) { return null; } //创建根节点 TreeNode root = new TreeNode(preorder[preIndex]); //在中序遍历的数组当中,找到当前根节点所在位置,此处我们需要额外定义一个findValInorder方法 int index = findValInorder(inorder,preorder[preIndex],inbegin,inend); preIndex++; //使用递归遍历来创建左树和右树 //注意是先创建我们的左树,在创建我们的右树 root.left = buildTreeChild(preorder,inorder,inbegin,index - 1); root.right = buildTreeChild(preorder,inorder,index + 1,inend); return root; } //此方法用于返回当前根节点在中序遍历结果中的位置,key为我们当前根节点的val值 public int findValInorder(int[] inorder,int key,int inbegin,int inend) { //注意是小于等于 for(int i = inbegin;i <= inend;i++) { if(inorder[i] == key) { return i; } } //没找到返回-1 return -1; } public TreeNode buildTree(int[] preorder, int[] inorder) { //前序和中序都不能为空,不然无法构建二叉树 if(preorder == null || inorder == null) { return null; } if(preorder.length == 0 || inorder.length == 0) { return null; } return buildTreeChild(preorder,inorder,0,inorder.length - 1); } }
注意:在一直前序和中序的情况下我们递归创建二叉树的左树和右树的时候一定是先创建我们的左树,再创建我们的右树,原因是中序遍历的顺序是左中右,所以当我们在卡奴性遍历的时候找到我们的中的时候,肯定是先创建我们的左树.再创建我们的右树
最后总结下时间复杂度和空间复杂度:
时间复杂度:O(N)
空间复杂度:O(N)
总结
一般来说我们可以根据前序和中序构造二叉树,可以根据中序和后序来构造二叉树,但是不能根据前序和后序来构造二叉树,因为前序和中序都可以确定我们的根节点,那么由谁来确定我们的左树和右树呢?所以必须包含我们的中序遍历的结果来确定我们的左树和右树.