LeetCode 105. 从前序与中序遍历序列构造二叉树
2020-05-22 16:04:22来源:博客园 阅读 ()
LeetCode 105. 从前序与中序遍历序列构造二叉树
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 105. 从前序与中序遍历序列构造二叉树
题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder =?[3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
前序遍历:根左右
中序遍历:左根右
首先很容易得到前序遍历的首个元素就是树的根,若跟元素为root,那么:
- 在中序遍历数组root元素的左侧部分就是树的左子树[0,R-1];
- 在中序遍历数组root元素的右侧部分就是树的右子树[R+1,length];
且: - 前序遍历的[1,R+1]是根的左子树;
- 前序遍历的[R+2,length]是根的右子树;
根据以上分析是可以递归重建二叉树的;
思路1-分割数组对应到子树重建
根据上面的分析,分割数组,每次新建当前节点为上层的子节点,直至处理完数组;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 分割数组需要的空间
思路2-不分割数组,控制双指针移动构建
因为递归分割需要创建新数组,所以思路1是非常耗时的,如果直接对原数组元素处理不用新建数组将有很大的提速;
先序遍历的[0]在中序遍历里的位置若为i,那么i-1在顺序上是两个遍历处理的左子树的最后一个节点,i+1以及之后的节点就是右子树了;
那么可以以这个条件作为构建左子树完毕的退出条件,退出后继续构建右子树;
所以,记录双指针分别对应两个遍历,i-先序遍历,j-中序遍历:
- [i]!=[j],递归构建左子树,i++;
- [i]==[j],i++,j++,跳过根节点,开始递归构建右子树;
- j==length构建完毕;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 递归栈的深度,最差时
算法源码示例
package leetcode;
import java.util.Arrays;
/**
* @author ZhouJie
* @date 2020年5月22日 下午1:28:22
* @Description: 105. 从前序与中序遍历序列构造二叉树
*
*/
public class LeetCode_0105 {
}
// Definition for a binary tree node.
class TreeNode_0105 {
int val;
TreeNode_0105 left;
TreeNode_0105 right;
TreeNode_0105(int x) {
val = x;
}
}
class Solution_0105 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午1:29:25
* @param: @param preorder
* @param: @param inorder
* @param: @return
* @return: TreeNode_0105
* @Description: 1-分割数组对应到子树递归处理;
*
*/
public TreeNode_0105 buildTree_1(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
} else {
TreeNode_0105 root = new TreeNode_0105(preorder[0]);
for (int i = 0; i < inorder.length; i++) {
if (preorder[0] == inorder[i]) {
root.left = buildTree_1(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
root.right = buildTree_1(Arrays.copyOfRange(preorder, i + 1, preorder.length),
Arrays.copyOfRange(inorder, i + 1, inorder.length));
break;
}
}
return root;
}
}
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午2:02:20
* @param: @param preorder
* @param: @param inorder
* @param: @return
* @return: TreeNode_0105
* @Description: 2-直接在数组上递归,不分割数组,效率高;
*
*/
private int indexPreorder = 0;
private int indexInorder = 0;
public TreeNode_0105 buildTree_2(int[] preorder, int[] inorder) {
return buildHelper(preorder, inorder, null);
}
private TreeNode_0105 buildHelper(int[] preorder, int[] inorder, TreeNode_0105 node) {
if (node != null && node.val == inorder[indexInorder] || indexInorder == preorder.length) {
return null;
}
// 开始构建左子树
TreeNode_0105 root = new TreeNode_0105(preorder[indexPreorder]);
// 先从preorder开始处理,当处理到等于inorder[0]的节点时,表明根的左子树已经构建完成,可以开始递归构建根的右子树了
if (preorder[indexPreorder] == inorder[indexInorder]) {
indexPreorder++;
indexInorder++;
} else {
indexPreorder++;
root.left = buildHelper(preorder, inorder, root);
indexInorder++;
}
// 对于根而言,开始右子树的递归构建
root.right = buildHelper(preorder, inorder, node);
return root;
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12937442.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash