最近一直在想办法刷算法题。有高手说过：算法题都是有套路,有框架的。
也看了高手写的文章，总结了好几个模板。但一直体会不透彻。
今天偶然做了三道二叉树的题。突然觉得好像有那么点意思。

第一道题目

对一个二叉树的每一层，都进行遍历，然后把每一层的放在一起返回结果。

我看题解里很多人说什么BFS啊，DFS什么的，我也不是很懂（我太菜了）。我最先想到的
这不就是一个前序遍历吗？只需要在遍历的时候，记录下来这是哪一层的就行了啊。

思路：用一个HashMap，以层数为Key，对应一个list，list里面就放这一层的元素。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
	//用于记录的map
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        search(root, 0, map);
        List<List<Integer>> result = new LinkedList<>();
        Set<Integer> s = map.keySet();
	//把每一层的结果放到需要返回的list里面去
        for (Integer key : s) {
            result.add(map.get(key));
        }
        return result;
    }
    
    public void search(TreeNode root, Integer deep, HashMap<Integer, List<Integer>> map) {
	//递归终止条件
        if (root == null) return;
        List<Integer> list;
	//将这一层的结果放进去
        if (!map.containsKey(deep)) {
            list = new LinkedList<>();
        } else {
            list = map.get(deep);
        }
        list.add(root.val);
        map.put(deep, list);
	//遍历下一层
        search(root.left, deep + 1, map);
        search(root.right, deep + 1, map);
    }
}

这样写很简单的吧，时间复杂度O(N) 和节点数量相关。空间复杂度O(N)，将每一个节点都需要记录下来。

第二道题目

锯齿形遍历，就是先从左往右，再从右往左。
和上一题的区别无非就是变成了“奇变偶不变”。
我们只需将看看层次是不是奇数，是的话就将它的结果翻转一下，不就成了从右往左了吗。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        search(root, 0, map);
        List<List<Integer>> result = new LinkedList<>();
        Set<Integer> s = map.keySet();
        for (Integer key : s) {
            List<Integer> list = map.get(key);
	    //判断下是否需要翻转
            if (key % 2 != 0)
                Collections.reverse(list);
            result.add(list);
        }
        return result;
    }

    public void search(TreeNode root, Integer deep, HashMap<Integer, ArrayList<Integer>> map) {
        if (root == null) return;
        ArrayList<Integer> list;
        if (!map.containsKey(deep)) {
            list = new ArrayList<>();
        } else {
            list = map.get(deep);
        }
        list.add(root.val);
        map.put(deep, list);

        search(root.left, deep + 1, map);
        search(root.right, deep + 1, map);
    }


}

第三道题目

这次要求从下往上层次遍历，那肯定一开始就想到了，把第一题的层次翻转一下不久好了吗？
于是就这么简单：

	public List<List<Integer>> levelOrderBottom(TreeNode root) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        search(root, 0, map);
        List<List<Integer>> result = new LinkedList<>();
        List<Integer> s = new ArrayList<>(map.keySet());
	//将层次顺序翻转
        Collections.reverse(s);
        for (Integer key : s) {
            result.add(map.get(key));
        }
        return result;
    }

    public void search(TreeNode root, Integer deep, HashMap<Integer, ArrayList<Integer>> map) {
        if (root == null) return;
        ArrayList<Integer> list;
        if (!map.containsKey(deep)) {
            list = new ArrayList<>();
        } else {
            list = map.get(deep);
        }
        list.add(root.val);
        map.put(deep, list);

        search(root.left, deep + 1, map);
        search(root.right, deep + 1, map);
    }

这三道题本质上就是同一个框架：二叉树的前序遍历，稍作细节上的改动，就能解决许多问题。学习算法，最重要的就是要对算法的本质思想进行总结。才能做到一力降十会。