查看原文
其他

591,二叉树的垂序遍历

博哥 数据结构和算法 2022-05-01

问题描述



来源:LeetCode第987题

难度:困难


给你二叉树的根结点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


问题分析



这题虽然是hard,但其实没有什么难度,做这题我最先想到的就是BFS遍历,如果当前节点是第m列,那么他的左子节点就是第m-1列,右子节点就是m+1列

所以我们可以从上到下一层一层的遍历,使用一个map来存储,map的key存储的是第几列,value是那个列的集合。辛辛苦苦写完之后发现运行不通过(代码放在了下面,有兴趣的可以看下),这是因为题中有这样一句话,如果同行同列上有多个结点,则按结点的值从小到大进行排序。也就是说如果两个节点位置重合了还要按照大小进行排序。


所以这题我们只能按照常规方式来解决,就是先记录下每个节点的值和坐标,最后再把他们按照同一列的顺序放到集合中,关于二叉树的遍历有多种,我们之前也介绍过一些

373,数据结构-6,树

488,二叉树的Morris中序和前序遍历

来看下代码

public List<List<Integer>> verticalTraversal(TreeNode root) {
    //list集合中的元素是一个数组,每个数组的长度都是3,第1个值表示
    //节点的值,第2个和第3个值表示节点的横坐标和竖坐标
    List<int[]> mList = new ArrayList<>();
    //计算所有节点的值和坐标,根节点的坐标是(0,0)
    dfs(root, 00, mList);
    //排序,排序的原则是先排左边一列,所以首先比较的是数组的第3个值(
    //纵坐标),然后每一列从上到下也就是数组的第2个值(横坐标),如果
    //前面两个值是一样的说明他们的坐标重合了,要按值从大到小排序
    Collections.sort(mList, (arr1, arr2) -> {
        //先按照纵坐标排序
        if (arr1[2] != arr2[2])
            return arr1[2] - arr2[2];
        if (arr1[1] != arr2[1])
            return arr1[1] - arr2[1];
        //如果坐标一样,再按照值排序
        return arr1[0] - arr2[0];
    });

    //把节点的值进行垂序分类
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());
    //因为上面排序了,所以这里首先遍历的就是最左边一列的值,
    //然后是第二列……
    for (int i = 0; i < mList.size(); i++) {
        //取出数组(包含当前节点的值和坐标)
        int[] arr = mList.get(i);
        //当前节点的值
        int value = arr[0];
        //如果当前节点和前一个节点不在同一列,说明到下一
        //列了,需要初始化下一列的集合
        if (i > 0 && arr[2] != mList.get(i - 1)[2])
            res.add(new ArrayList<>());
        //把当前节点的值添加到当前列中
        res.get(res.size() - 1).add(value);
    }
    return res;
}

private void dfs(TreeNode node, int i, int j, List<int[]> mList) {
    if (node == null)
        return;
    //把当前节点的值和坐标加入到集合中,当前节点的坐标是(i,j)
    mList.add(new int[]{node.val, i, j});
    //遍历左子节点
    dfs(node.left, i + 1, j - 1, mList);
    //遍历右子节点
    dfs(node.right, i + 1, j + 1, mList);
}


//错误的代码(同一行和同一列的两个值没有按照大小进行排序)

public List<List<Integer>> verticalTraversal(TreeNode root) {
    Map<Integer, ArrayList<Integer>> map = new HashMap<>();
    //存放节点的值
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    //存放每个节点对应第几列
    Queue<Integer> lineQueue = new LinkedList<>();
    //根节点是第0列,他左子节点的列是负数,右子节点的列是正数
    nodeQueue.add(root);
    lineQueue.add(0);
    //记录最小的列,也就是最左边的列
    int mineLine = 0;
    while (!nodeQueue.isEmpty()) {
        //当前节点及对应的列出队
        TreeNode curNode = nodeQueue.poll();
        int line = lineQueue.poll();
        //记录最左边的列
        mineLine = Math.min(mineLine, line);
        //如果对应列的集合不存在就初始化一个
        if (!map.containsKey(line)) {
            map.put(line, new ArrayList<>());
        }
        //把当前节点对应的值加入到当前节点对应列的集合中
        map.get(line).add(curNode.val);
        //左子节点不为空,就把他以及他所在的列加入到队列中
        if (curNode.left != null) {
            nodeQueue.add(curNode.left);
            lineQueue.add(line - 1);
        }
        //右子节点同上
        if (curNode.right != null) {
            nodeQueue.add(curNode.right);
            lineQueue.add(line + 1);
        }
    }
    //把Map转化为List,map中key存储的是第几列,
    //value存储的是每一列的集合
    List<List<Integer>> res = new ArrayList<>();
    int end = mineLine + map.size();
    for (int i = mineLine; i < end; i++) {
        res.add(map.get(i));
    }
    return res;
}


564,二叉树最大宽度

488,二叉树的Morris中序和前序遍历

464. BFS和DFS解二叉树的所有路径

456,解二叉树的右视图的两种方式


截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。


你点的每个赞,我都认真当成了喜欢

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存