【力扣每日一题】力扣987二叉树的垂序遍历

题目来源

力扣987二叉树的垂序遍历

题目概述

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

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

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

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

思路分析

我们可以使用层序遍历方式，遍历每一层的节点，计算它的列索引。 需要注意的是题目中只要求同行同列的节点需要排序。

代码实现

public class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<Integer>> indexAndValMap = new HashMap<>();
        Queue<IndexAndNode> parrentQueue = new LinkedList<>();
        Queue<IndexAndNode> sonQueue = new LinkedList<>();
        parrentQueue.add(new IndexAndNode(0, root));
        List<Integer> zeroList = new ArrayList<>();
        zeroList.add(root.val);
        indexAndValMap.put(0,zeroList);
        int min = 0;
        int max = 0;
        while (!parrentQueue.isEmpty()) {
            Map<Integer, List<Integer>> tempListMap = new HashMap<>();
            while (!parrentQueue.isEmpty()) {
                IndexAndNode poll = parrentQueue.poll();
                // 如果左孩子存在，加入临时队列
                if (poll.treeNode.left != null) {
                    min = Math.min(min, poll.index - 1);
                    sonQueue.add(new IndexAndNode(poll.index - 1, poll.treeNode.left));
                    if (!indexAndValMap.containsKey(poll.index - 1)) {
                        indexAndValMap.put(poll.index - 1, new ArrayList<>());
                    }
                    if (!tempListMap.containsKey(poll.index - 1)) {
                        tempListMap.put(poll.index - 1, new ArrayList<>());
                    }
                    tempListMap.get(poll.index - 1).add(poll.treeNode.left.val);
                }
                // 右孩子存在加入临时队列
                if (poll.treeNode.right != null) {
                    max = Math.max(max, poll.index + 1);
                    sonQueue.add(new IndexAndNode(poll.index + 1, poll.treeNode.right));
                    if (!indexAndValMap.containsKey(poll.index + 1)) {
                        indexAndValMap.put(poll.index + 1, new ArrayList<>());
                    }
                    if (!tempListMap.containsKey(poll.index + 1)) {
                        tempListMap.put(poll.index + 1, new ArrayList<>());
                    }
                    tempListMap.get(poll.index + 1).add(poll.treeNode.right.val);
                }
            }
            // 排序临时队列，加入结果队列map
            int tempMin = min;
            while(tempMin <= max) {
                List<Integer> tempList = tempListMap.get(tempMin);
                if (tempList == null) {
                    tempMin++;
                    continue;
                }
                Collections.sort(tempList);
                indexAndValMap.get(tempMin).addAll(tempList);
                tempMin++;
            }
            Queue<IndexAndNode> temp = parrentQueue;
            parrentQueue = sonQueue;
            sonQueue = temp;
        }
        // 结果队列map转list
        List<List<Integer>> res = new ArrayList<>();
        while(indexAndValMap.containsKey(min)) {
            res.add(indexAndValMap.get(min));
            min++;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(
                new Solution().verticalTraversal(
                        new TreeNode(3,new TreeNode(9),new TreeNode(20,new TreeNode(15),new TreeNode(7)))
                )
        );
    }
}

/**
 * 记录节点的列索引，方便计算孩子节点的列索引
 */
class IndexAndNode{
    int index;
    TreeNode treeNode;

    public IndexAndNode(int index, TreeNode treeNode) {
        this.index = index;
        this.treeNode = treeNode;
    }
}