[LeetCode] 987. Vertical Order Traversal of a Binary Tree

原题链接：https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

1. 题目介绍

Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

给出一个二叉树，按竖直的顺序遍历所有节点。
对于在坐标（X，Y）处的节点，它的左子节点的坐标是(X-1, Y-1)，右子节点的坐标是(X+1, Y-1)。
从X = 负无穷 到 X = 正无穷，无论竖直的直线接触到了哪些节点，我们都会以Y坐标递减的顺序，从上到下记录节点的值。
如果两个节点有同样的坐标值，优先记录val值较小的那个。
按照X坐标的顺序，每个X的坐标都有一个节点 val 值的 list 。把所有 X 坐标的 list 汇总起来，就是需要返回的答案。

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, 
we can assume the root node is at position (0, 0):
不失一般性，我们可以假定根节点的坐标是(0, 0)
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", 
the node value of 5 comes first since 5 is smaller than 6.
                  1: (0 , 0)
       2: (-1 , -1)            3: (1 , -1)
4:(-2, -2)  5:(0, -2)     6:(0, -2)   7:(2 , -2)

Note:
The tree will have between 1 and 1000 nodes.
节点的总数范围是1到1000
Each node’s value will be between 0 and 1000.
每一个节点的val值的范围是0到1000

2. 解题思路

本题的解题思路参考了LeetCode官方题解，感兴趣的读者可以直接去看原文： https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/solution/

拿到一个题，首先要对问题进行分解，估计一下，解决这个问题大致需要几个步骤，然后再逐个击破。
对于这道题，对题目进行分解之后，我觉得有如下几个步骤：
1 . 计算出每个节点的坐标
2 . 将每个坐标对应的节点val存储到一个数据结构里
3 . 按照顺序，提取对应坐标的val值

接下来分别想一想怎么完成上面的三个步骤，对其逐个击破。
对于第1个步骤，可以采用深度优先搜索的方式遍历整个树，使用递归为每个节点设定坐标。

对于第2个步骤，可以自己定义一个Location类，这个类存储了节点的坐标和 val 值，可以完成坐标和 val 值之间的映射。同时该类还需要实现 Comparable 接口。在 compareTo 方法中定义自己的比较规则。定义的比较规则应该是首先比较X的值，取最小的排在前面，当X值相同的时候，取Y较大的排在前面，当X、Y都相同的时候，取val值较小的排在前面。

对于第3个步骤，此时在Location类中已经按照顺序排好了节点，只要按照顺序提取 val 值即可。难点是把坐标相同的节点放在同一个 list 中，坐标不同的节点分开放。因此需要判断前一个List中的x值和要放入的Location类中的x值是否相同，如果不同，就新建一个List。

具体做法可以参考如下代码：
实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//定义Location类，包含节点的x、y坐标和val值
class Location implements Comparable<Location>{
    int x , y , val;
    Location(int x, int y ,int val){
        this.x = x;
        this.y = y;
        this.val = val;
    }
    public int compareTo(Location that){
        if(this.x != that.x){
            return Integer.compare(this.x , that.x);
            //this.x 较大时，返回1， 较小时，返回-1
            //compare(x,y)函数的源码:
            //return (x < y) ? -1 : ((x == y) ? 0 : 1);
        }else if (this.y != that.y){
            //y是降序排列的，和x相反，因此
            //this.y 较大时，返回-1， 较小时，返回1,和this.x的正好相反
            return (this.y > that.y) ? -1: ((this.y == that.y) ? 0 : 1);
        }else{
            return Integer.compare(this.val , that.val);
        }
    }
}

class Solution {
    List<Location> l;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        l = new ArrayList();
        setXY(root, 0, 0);//遍历所有节点，设定X、Y的值
        Collections.sort(l);//对所有Location进行排序
        
        List<List<Integer>> ans = new ArrayList();
        ans.add(new ArrayList<Integer>());//为了保证ans非空
        int prev = l.get(0).x;//设定为排在第一位的location的x值
        
        for(Location i : l){
            //如果x的值不同了，就应该新建一个List
            if(i.x != prev){
                prev = i.x;
                ans.add(new ArrayList<Integer>() );
            }
            //需要在ans最后一个list中添加当前Location的val值
            ans.get(ans.size() - 1).add( i.val );
        }
        return ans;
    }
    public void setXY(TreeNode root, int x, int y){
        if(root == null){
            return;
        }
        l.add( new Location( x , y , root.val));
        setXY(root.left , x-1 , y-1);
        setXY(root.right, x+1 , y-1);
    }
}

3. 参考资料

解题思路：
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/solution/

compareTo和compare方法的介绍和比较:
https://blog.csdn.net/fly910905/article/details/81670353
https://blog.csdn.net/fly_fly_fly_pig/article/details/82740277

关于Collections.sort()的使用：
https://blog.csdn.net/qq_23179075/article/details/78753136