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

Question

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

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

当我打印出 HashMap 的值时，我发现它有正确的元素组合在一起。

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

例如：

如果输入树是：

程序应该return：[[9], [3,15], [20], [7]]

然而，我的 returns: [[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

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

HashMap 不保持顺序，即使保持顺序，您也是按深度优先顺序向 HashMap 添加元素，这意味着先添加根。所以在你的输出中你没有得到预期的顺序是很正常的。

您应该改为按键值的顺序迭代地图。
当多个值被添加到同一个映射条目时（因为键是相同的），您也按照访问它们的顺序添加它们。但是这个顺序不能保证是所需的顺序：深度优先迭代将在树中上下移动，因此不能保证您会在处理下层节点之前先处理上层节点。如果你想要那个，你需要一个 breadth-first。或者，您可以将 y-coordinate（级别）作为参数传递。
当两个节点具有相同的 x 和 y 坐标时，应按升序报告它们的值。你对此没有任何规定。如果您坚持使用 depth-first，那么在地图条目中您将需要另一个由 y-coordinate 键入的地图。然后，当您发现当前 y-coordinate 已经有一个条目时，您应该确保以正确的顺序添加当前节点的值。请注意，这会为您的数据结构添加一个嵌套级别。最好先添加值而不排序，然后在算法的最后阶段遍历完整的数据结构并对所有这些小子数组进行排序。

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

Vertical Order Traversal of a Binary Tree using dfs and Map

java

tree

binary-tree

tree-traversal