traverse的时候要知道每个NODE是在第几列。
我用的方法是DFS，传入的时候记录NODE是左起第几列，还要知道最左边是第几列。
一开始最左边是第0列，ROOT是坐起第0列。
进入方程之后，如果这一列不存在，列数>=size()，手动添加。其实相当于往右添加列
然后看左边是否有left child，有的话它的列数是 当前列数-1，如果他比最左列还左，他成为最左列，并且塞一个新的LIST在最左边。 相当于往左添加列
然后这个题有一个很大的问题，他要求每一列的顺序必须是从上往下的。例子中最后一个，结果是
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
如果按照DFS来遍历，结果是
[
[4],
[9,5],
[3,0,1],
[2,8],
[7]
]
注意第三列，一个是2 8， 一个是8 2.
都写完了才发现这个问题，其实这个题就相当于要求用BFS，只有BFS是按照层数来的，题设里一开始并没有说这个要求……
哇呀呀..我生~ 气~ 啦~
但是我懒得改了，愤怒地新建了一个类，添加的时候记录了每个点的level，最后重新按LEVEL SORT了一下。。。。。。
二刷再BFS吧。。。
public class Solution
{
public class Node
{
int val;
int level;
public Node(int val, int level)
{
this.val = val;
this.level = level;
}
}
int leftmost = 0;
public List<List<Integer>> verticalOrder(TreeNode root)
{
List<List<Node>> res = new ArrayList<List<Node>>();
List<List<Integer>> realRes = new ArrayList<List<Integer>>();
if(root == null) return realRes;
traverse(res,root,0,0);
for(int i = 0; i < res.size();i++)
{
List<Node> list2 = res.get(i);
List<Integer> list1 = new ArrayList<Integer>();
Collections.sort(list2,new com());
for(int j = 0; j < list2.size();j++)
{
list1.add(list2.get(j).val);
}
realRes.add(new ArrayList<>(list1));
}
return realRes;
}
public class com implements Comparator<Node>
{
public int compare(Node a, Node b)
{
return Integer.compare(a.level,b.level);
}
}
public void traverse(List<List<Node>> res, TreeNode root, int diff,int level)
{
if(root == null) return;
int index = diff-leftmost;
Node tempNode = new Node(root.val,level);
if(index >= res.size() && diff >= 0)
{
List<Node> tempList = new ArrayList<Node>();
tempList.add(tempNode);
res.add(new ArrayList<>(tempList));
}
else res.get(diff-leftmost).add(tempNode);
if(root.left != null)
{
if(diff-1 < leftmost)
{
leftmost = diff - 1;
res.add(0,new ArrayList<Node>());
}
}
traverse(res,root.left,diff-1,level+1);
traverse(res,root.right,diff+1,level+1);
}
}
二刷。
这个题也有印象，有个小坑。 就是DFS的时候左支的最右点如果超过右支最左点，遍历顺序就和要假如的顺序相反，就需要多一个class...
这么说很含糊，具体情况看例子里的[2,8]和[8,2]就行了。。
二刷用的BFS。BFS的话，同列里的顺序正好是BFS从上到下的顺序。
剩下的问题就是记录每个点是第几列。把ROOT作为0，左边-1，右边+1,就行了。。
做完之后考虑了一下，不用MAP也是可以的。 知道最左最右，是可以通过相对位置来添加的，就像一刷那这样。
Time : O(n)bfs + O(n) addition
Space : O(n)queue + O(n) map(not necessary)
public class Solution {
public class Node {
TreeNode node;
int level;
public Node (TreeNode n, int l) {
node = n;
level = l;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<Node> q = new LinkedList<>();
Node temp = null;
q.offer(new Node(root, 0));
int min = 0;
int max = 0;
while (!q.isEmpty()) {
temp = q.poll();
// add to vertical map
if (!map.containsKey(temp.level)) {
map.put(temp.level, new ArrayList<Integer>());
}
map.get(temp.level).add(temp.node.val);
// update max and min
min = Math.min(temp.level, min);
max = Math.max(temp.level, max);
// add neighbor to queue
if (temp.node.left != null) {
q.offer(new Node(temp.node.left, temp.level - 1));
}
if (temp.node.right != null) {
q.offer(new Node(temp.node.right, temp.level + 1));
}
}
for (int i = min; i <= max; i++) {
if (map.containsKey(i)) {
res.add(map.get(i));
}
}
return res;
}
}
做完看了一下Discussion区，有人用的TreeMap，似乎就是给Key排序了，那么就不用手动记录MIN和MAX了，更方便。三刷再说。