［抄题］：
给定二叉树，返回其节点值的垂直遍历顺序。 (即逐列从上到下)。
如果两个节点在同一行和同一列中，则顺序应 从左到右。
给定一个二叉树 {3,9,20,#,#,15,7}
3
/\
/ \
9 20
/\
/ \
15 7
返回垂直遍历顺序：[[9],[3,15],[20],[7]]
给定一个二叉树 {3,9,20,#,#,15,7}
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
返回垂直遍历顺序：[[4],[9],[3,0,1],[8],[7]]
[暴力解法]：
时间分析：
空间分析：
［思维问题］：
- 完全不知道怎么找出数学关系，找出变化关系：列数从小到大，同一列时行数从小到大，从左到右
- 从左到右要用bfs来实现：添加一个点、扩展；添加一个点、扩展
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 不知道bfs怎么写，怎么扩展：树上进行的BFS是用左右节点来扩展的
- queue是用linkedlist实现的，不要死记硬背，直接联想图吧 用的是.poll()方法
- 已经创建出了qcol对象，判断它是否为空，用isempty()，没有对象才用null，要理解含义
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
树上进行的BFS是用左右节点来扩展的
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
- 每一列后面都是数字链表，用hashmap的value存储数字链表，和叶子顺序遍历相同
- 用两个队列：列数也是不断添加一个列、扩展到新涉及的列；添加一个列、扩展到新涉及的列
- hash.keySet()方法（方法也符合骆驼命名法）表示取出哈希表的所有key,Collections.min方法表示取出没有排序的哈希表的其最小值
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/*
* @param root: the root of tree
* @return: the vertical order traversal
*/
public List<List<Integer>> verticalOrder(TreeNode root) {
//corner case
List<List<Integer>> ans = new ArrayList<>();
HashMap<Integer, List<Integer>> hash = new HashMap<>(); if (root == null) {
return ans;
}
Queue<Integer> qCol = new LinkedList<>();
Queue<TreeNode> qNode = new LinkedList<>();
//bfs
qCol.offer(0);
qNode.offer(root); while (!qCol.isEmpty()) {
int col = qCol.poll();
TreeNode node = qNode.poll(); hash.putIfAbsent(col,new ArrayList());
hash.get(col).add(node.val); if (node.left != null) {
qCol.offer(col - 1);
qNode.offer(root.left);
} if (node.right != null) {
qCol.offer(col + 1);
qNode.offer(root.right);
}
} for (int i = Collections.min(hash.keySet()); //
i <= Collections.max(hash.keySet()); i++) {
ans.add(hash.get(i));
} return ans;
}
}