二叉树遍历系列

• 144.二叉树的前序遍历
• 94.二叉树的中序遍历
• 145.二叉树的后续遍历
• 102.二叉树的层序遍历
• 107.二叉树的层序遍历II
• 103.二叉树的锯齿形层序遍历（之字形遍历）
• 199.二叉树的右视图

1.问题

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]

解释：
列 -1 ：只有结点 9 在此列中。
列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列 1 ：只有结点 20 在此列中。
列 2 ：只有结点 7 在此列中。

示例 2

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]

解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。

示例 3

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]

解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

• 树中结点数目总数在范围 [1, 1000] 内
• 0 <= Node.val <= 1000

2.解题思路

从示例可以得出，最终答案是先按列号从小到大排列，列号相同再按行号从小到大，行号相同再按值从小到大输出。因而我们在遍历二叉树时需要统计各个节点(列号，行号，值)的三元组，然后按照列号、行号、值的升序排列，最后输出结果。

• 定义一个map，key为节点，value存储该节点的列号，行号，值
• 深度优先算法，遍历各个节点，记录各节点 列号、行号、值，保存至map中
• 对map的values按照排序规则进行排序

复杂度：

• 时间复杂度：令总节点数量为 n，填充哈希表时进行树的遍历，复杂度为 O(n)；构造答案时需要进行排序，复杂度为 O(nlog⁡n)。整体复杂度为 O(nlog⁡n)
• 空间复杂度：O(n)

作者：宫水三叶
链接：https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/solutions/906335/gong-shui-san-xie-yi-ti-shuang-jie-dfs-h-wfm3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3.代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //记录节点 列号、行号、值
    Map<TreeNode, int[]> map = new HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        //示例规则，先按列号从小到大排列，列号相同再按行号从小到大，行号相同再按值从小到大输出
        //定义一个map,key为节点，value存储该节点的 列号，行号，值
        //深度优先算法，遍历各个节点，记录各节点 列号、行号、值，保存至map中
        //对map的values按照排序规则进行排序
        
        //root - map
        map.put(root,new int[]{0,0,root.val});
        dfs(root);

        //各节点 遍历的信息列表
        List<int[]> list=new ArrayList<>(map.values());
        //排序
        Collections.sort(list, (a,b)->{
            //优先按列比较
            if(a[0]!=b[0]){
                return a[0]-b[0];
            }
            //其次 按行号比较
            if(a[1]!=b[1]){
                return a[1]-b[1];
            }
            //最后，按值比较
            return a[2]-b[2];
        });

        //遍历list，输出结果集
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> tmp;
        for(int i=0;i<list.size();){
            int j=i;
            tmp=new ArrayList<>();
            //列号相同的
            while(j<list.size() && list.get(j)[0]==list.get(i)[0]){
                tmp.add(list.get(j)[2]);
                j++;
            }
            res.add(tmp);
            i=j;
        }
        return res;
    }

    private void dfs(TreeNode node){
        if(null==node){
            return;
        }
        int[] nodeColRowVal=map.get(node);
        int nodeCol=nodeColRowVal[0];
        int nodeRow=nodeColRowVal[1];
        int value=nodeColRowVal[2];

        //左子树
        if(null!=node.left){
            map.put(node.left, new int[]{nodeCol-1, nodeRow+1, node.left.val});
            dfs(node.left);
        }

        //右子树
        if(null!=node.right){
            map.put(node.right, new int[]{nodeCol+1, nodeRow+1, node.right.val});
            dfs(node.right);
        }
    }
}