105. Construct Binary Tree from Preorder and Inorder Traversal根据前中序数组恢复出原来的树
[抄题]:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
[暴力解法]:
时间分析:
空间分析:
[优化后]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
if (preStart > preEnd || inStart > inEnd) 退出条件是>,因为等于的时候还可以继续新建节点
[思维问题]:
不知道怎么dc:参数就是数组的index就行了,分成start1 end1 start2 end2,多开几个变量就行了
[英文数据结构或算法,为什么不用别的数据结构或算法]:
[一句话思路]:
通过hashmap记录下pre的中节点在in中的位置,然后左右dc
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- HashMap<Integer, Integer> map 函数中已经建立好了的map不需要加括号,新建map才需要
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
不知道怎么dc:参数就是数组的index就行了,分成start1 end1 start2 end2,多开几个变量就行了
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[算法思想:迭代/递归/分治/贪心]:
[关键模板化代码]:
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
[是否头一次写此类driver funcion的代码] :
[潜台词] :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//corner case
if (preorder == null && inorder == null) return null; //initialization : put all the inorder into map
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < inorder.length; i++)
map.put(inorder[i], i); //return
return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
} public TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> map) {
//exit if the bounds exceeds
if (preStart > preEnd || inStart > inEnd) return null; //build a new root
TreeNode root = new TreeNode(preorder[preStart]);
int inIdx = map.get(root.val);
int numsLeft = inIdx - inStart; //divid and conquer to form left and right
root.left = buildTreeHelper(preorder, preStart + 1, preEnd, inorder, inStart, inIdx - 1, map);
root.right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd, inorder, inIdx + 1, inEnd, map); return root;
}
}
最新文章
- 网站实现微信登录之嵌入二维码——基于yii2开发的描述
- MySQL的InnoDB索引原理详解
- [实践] Android5.1.1源码 - 在Framework中添加自定义系统服务
- 编译WebRTC遇到的问题总结
- 如何定位web前后台的BUG
- Centos|RHEL7以前解决网卡eth0相关问题
- PHP json数据格式化方法
- 用JS制作简易选项卡
- JAVA 处理程序异常,(try、catch、finally),(thorws)
- poj 3083 Children of the Candy Corn (广搜,模拟,简单)
- jetty之嵌入式运行jetty
- YAML书写规范
- sql集锦
- 【学习笔记】启动Nginx、查看nginx进程、查看nginx服务主进程的方式、Nginx服务可接受的信号、nginx帮助命令、Nginx平滑重启、Nginx服务器的升级
- MT【314】正切比值
- 运维中的日志切割操作梳理(Logrotate/python/shell脚本实现)(转)
- Oracle_高级功能(10) 备份恢复
- 使用nginx搭建tomcat集群配置
- 2016-2017-2 《Java程序设计》第二周学习总结
- Eclipse / Pycharm | 使用过程中的一些问题笔记