使用dfs和Map的二叉树垂直顺序遍历

Question

我正在尝试对二叉树进行垂直顺序遍历，这个问题：https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

我的方法是：我对树中的每个节点进行深度优先搜索，其中根为0。左边的任何内容都是当前根-1，右边的任何内容都是当前根1。我还有一个HashMap，其中键是节点的值（具有相同位置匹配的值），值是具有相同位置（键值）的所有树节点的链接列表。

当我打印HashMap的值时，我看到它将正确的元素分组在一起。

问题是，当我返回最终列表时，整数列表的顺序不正确，应该是从最大的负数到最大的正数-相反，与根位置相同的元素首先被打印出来。我想这是因为我不能用负数作为HashMap的键，但我想不出一个解决方法。

例如：

如果输入树为：

程序应该返回：[[9]，[3,15]，[20]，[7]]

但是，我的返回：[[3,15]，[9]，[20]，[7]]

/**
 * 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 {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        /*dfs getting value of node & adding it to list*/
        List<List<Integer>> list = new ArrayList<>();
        
        Map<Integer, List<Integer>> map = new HashMap<>();
        
        if(root == null) {
            return list;
        }
        
        dfs(root, map, 0);
        
        for(Map.Entry<Integer, List<Integer>> m : map.entrySet()) {
            List<Integer> temp = new ArrayList<>();
            for(int i : m.getValue()) {
                temp.add(i);
            }
            list.add(temp);
        }
        
        return list;
    }
    
    public static void dfs(TreeNode root,  Map<Integer, List<Integer>> map, int curVal) {
        if(root == null) {
            return;
        }
        
        // System.out.println("root val = " + root.val);
        // System.out.println("curVal = " + curVal);
        
        if(map.containsKey(curVal)) {
            List temp = map.get(curVal);
            temp.add(root.val);
            map.put(curVal, temp);
        }
        else {
            List<Integer> tempList = new ArrayList<>();
            tempList.add(root.val);
            map.put(curVal, tempList);
        }
        
        dfs(root.left, map, curVal - 1);
        dfs(root.right, map, curVal + 1);
    }
}

Answer 1

负键没有问题，就是少了几个东西。

>

相反，您应该按照其键值的顺序迭代映射。

当多个值被添加到同一个地图条目（因为键是相同的）时，您也将按照访问它们的顺序添加它们。但是这个顺序不能保证是所需的顺序：深度第一次迭代将在树中上下移动，所以不能保证您将在较低节点之前处理较高节点。如果你想要这样，你需要广度优先。或者，您可以将y坐标（级别）作为参数传递。

当两个节点具有相同的x和y坐标时，应按升序报告它们的值。你没有这方面的准备。如果您首先坚持使用深度，那么在地图条目中，您将需要另一个由y坐标设置关键帧的地图。然后，当您发现当前y坐标已经存在一个条目时，您应该确保以正确的顺序添加当前节点的值。请注意，这将为数据结构添加嵌套级别。最好先添加值而不进行排序，然后在算法的最后阶段遍历完整的数据结构并对所有这些小数组进行排序。