昨天专利评审，挺焦虑的，怕不能通过，中午看到益达的一句话很治愈：焦虑的时候干就好了
第一题 从尾到头打印链表
解法很简单，链表放入stack，然后pop出来放入arrlist。
这里看到了ArrayList。举一反三认识一下ArrayList。
1 首先它的数据结构其实是一个动态数组，线程不安全的，允许元素为null。因为是数组，内存空间是连续的，代表他读写的效率很高，但是空间效率就不高了。
2 默认大小是10，当集合中的元素超出这个容量，便会进行扩容操作，扩容的大小默认是1.5倍，如果扩容一半不够，就用目标的size作为扩容后的容量，至于为啥是1.5，太大占据空间，太小效率不高，1.5的出处母鸡。
3 如果想线程安全就用vector，区别是vector加了synchozied
4 使用arrayList的get方法，是获取第一个元素快还是获取最后一个元素快?一样快，参加源码说明基本是个固定时间。因为ArrayList是使用数组作为内部存储结构，访问数组中任何一个元素所花费的时间是相等的
public ArrayListprintlist(ListNode listNode) {Stackstack = new Stack<>();while (listNode != null) { stack.add(listNode.val); listNode = listNode.next; } ArrayList ret = new ArrayList<>();
while (!stack.isEmpty()) {
ret.add(stack.pop());
}
return ret;
}
第二题
重建二叉树
解题思路：
前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。即根节点是3，那么在前序中，左边数是9，右边数是 20 15 7，中序中左边数是9 左边数是15 20 7.
设想这么一个TreeNodere(int[] pre,intstartPre,intendPre,int[] in,intstartIn,intendIn)，pre代表前序遍历，in代表中序。那么左边数就是（pre,startPre+1,startPre+i-startIn,in,startIn,i-1）即TreeNodere（pre,1,1,in,0,0）
右边树就是re(pre,startPre+i-startIn+1,endPre,in,i+1,endIn)，也就是（pre,2,4,in,2,4）。整个算法好理解，但是递归使用还是比较难理解，按照自己的思路加了注释，不一定对，先这样背
public class ReBinaryTree {public MapTreehash = new HashMap<>();public TreeNode reconsBinarytree(int[] pre,int[] inorder) {for(int i=0;ipreRight) return null;
TreeNode root = new TreeNode(pre[preLeft]);
//计算左边数大小left TreeSize
int lefttreeSize = Treehash.get(inorder[preLeft])-preLeft;
//下面的边界值完全可以把前序以及中序放在一起，查看左边树，右边树在前序以及中序的位置看出来
root.left = reConstructBinaryTree(pre,preLeft+1,preLeft+lefttreeSize,inorder,iLeft,iLeft+lefttreeSize-1);
root.right = reConstructBinaryTree(pre,preLeft+lefttreeSize+1,preRight,inorder,iLeft+lefttreeSize+1,iRight);
return root;
}
}
https://www.jianshu.com/p/07ac60fd2e5c 参考
