leetCode进阶算法题+解析（二十二）
二叉树的前序遍历
题目：给定一个二叉树，返回它的 前序 遍历。
题目截图
思路：这个题也没啥思路可说的，一个递归一个迭代，我都写一遍就行了。然后之前做过一个中序排列。刚刚还看到下一道题是后续排列。一起做了得了，我去写代码了。
首先是递归实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> res;
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<Integer>();
pre(root);
return res;
}
public void pre(TreeNode root){
if(root==null) return;
res.add(root.val);
pre(root.left);
pre(root.right);
}
}
迭代实现:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(root!=null || !stack.isEmpty()){
if(root!=null){
res.add(root.val);
if(root.left != null)stack.push(root.left);
root = root.left;
}else{
root = stack.pop();
if(root.right != null)stack.push(root.right);
root = root.right;
}
}
return res;
}
}
不得不说反正我这两个代码还是递归性能比较高。不过我看了人家的迭代实现，比我要好看多了。。。我直接贴代码了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
stack.add(root);
while(!stack.isEmpty()){
root = stack.pollLast();
res.add(root.val);
if(root.right != null){
stack.add(root.right);
}
if(root.left != null){
stack.add(root.left);
}
}
return res;
}
}
emmmm....事实证明这段代码人家提交超过百分百，我提交好几次也都只超过百分之五十八。。和我之前的一样的。。。行了行了，就这样了，下一题是后续遍历。
二叉树的后序遍历
题目：给定一个二叉树，返回它的 后序 遍历。进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路：题目截图就不截图了，知道是后序遍历就行了，我直接贴代码了。
递归版本：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<Integer>();
post(root);
return res;
}
public void post(TreeNode root){
if(root == null) return;
post(root.left);
post(root.right);
res.add(root.val);
}
}
迭代版本：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<Integer>();
if(root == null) return res;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
stack.add(root);
while(!stack.isEmpty()){
root = stack.poll();
if(root.left !=null ) stack.push(root.left);
if(root.right != null) stack.push(root.right);
res.addFirst(root.val);
}
return res;
}
}
其实这个题就是上题的逆思路。递归就不说了，迭代的话如果是前序是 当前 + 左 +右。后续是 左 + 右 +当前。
其实左右是一样的，但是当前要去后面。 换个思路 如果实现了 当前 +右 +左 则倒过来直接就是后序遍历了。就这个思路。然后每次add都是添加到第一个，还有先放左再放右。
感觉也没啥说的，刚刚做才发现后序遍历是困难的，哈哈，突然对自己有信心了呢~~下一题了啊
LRU缓存机制
题目：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
思路：这个题怎么说呢，我觉得实现起来还是很简单的，尤其是进阶要求只要求了时间复杂度而没有空间复杂度。。我目前的想法是用LinkedHashMap。然后put判断下size，达到容量了则把第一个删了，然后后一个加上。没达到直接加。 然后get的时候先把这个key-value获取了，然后把这个key删除了，重新添加，保证用过的在最后，第一个的永远是最不活跃的那个。。差不多就这样，我去代码实现下。
尴尬了，我发现LinkedHashMap自带访问顺序，就是访问完移到最后，，，哈哈。其实这个类我早就知道，但是工作中几乎没用到过，只知道是Linked（链表）+HashMap的合体，本来我以为只是有序的map呢。。。刚刚要用了去百度了下api才发现不太多。。我用这个数据结构是不是太取巧了啊？不管了，反正第一版本先实现再说。
好了，在前人的肩膀上直接实现了：
class LRUCache {
LinkedHashMap<Integer,Integer> map;
public LRUCache(int capacity) {
this.map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return map.size() > capacity;
}
};
}
public int get(int key) {
return map.get(key)==null?-1:map.get(key);
}
public void put(int key, int value) {
map.put(key,value);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
我仅剩不多的自尊心告诉我这道题不是考对Linked Hash Map的熟悉程度的。。。我这是取巧了啊，我自己实现试试。
其实我觉得用LinkedList和HashMap也是可以实现的。链表存key，map的key还是key，value是value。然后链表就按照我刚刚说的，超了再放则删除第一个。重复访问则删除再添加保证访问的在最后。我去实现下看看。
自己手写出来了，效率啥的贼辣眼睛。。。我先贴出来：
class LRUCache {
int cap;
HashMap<Integer,Integer> map;
LinkedList<Integer> list;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<Integer,Integer>();
list = new LinkedList<Integer>();
}
public int get(int key) {
if(map.get(key) != null){
list.remove(Integer.valueOf(key));
list.add(key);
return map.get(key);
}
return -1;
}
public void put(int key, int value) {
if(list.size()==cap && !list.contains(key)){
Integer r = list.get(0);
list.remove(0);
map.remove(r);
list.add(key);
map.put(key,value);
}else if(list.contains(key)){//说明key已经存在，是更改值
list.remove(Integer.valueOf(key));
list.add(key);
map.put(key,value);
}else{
list.add(key);
map.put(key,value);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
就是linkedList 来排序， map来存值。难道是不难，就是很墨迹。这个题就这样了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，顺便祝大家工作顺顺利利，生活平平安安，周末愉快！
