使用 TreeMap 进行二叉树深度优先搜索的顶部视图

Question

这是我对二叉树编码忍者问题顶视图的尝试

https://www.naukri.com/code360/problems/top-view-of-binary-tree_799401?leftPanelTabValue=问题

我希望仅使用 TreeMap 来完成此操作。通过使用这种逻辑，我认为由于递归，TreeMap 应该只选取关键元素作为列，将值选取作为列的最顶层节点。我尝试制作一棵递归树，我认为还可以。然而，我得到了错误的输出。

由于TreeMap仅按排序顺序存储键，因此将它们取出用于俯视图也会更容易。我知道该行没有在任何地方使用，但我已经拿走了它。如果没有行变量，它不应该工作吗？因为递归应该能够处理深度优先搜索。以及用于在树图中插入的列变量。

它甚至没有通过任何测试用例。但我觉得根据递归树我应该得到完全正确的输出。或者也许，我把递归树弄错了。

对于列，仅当节点不存在时才插入该节点。如果它已经在那里，那么这是因为由于 DFS 的方式，它是该列中可能的最高节点。

因为它应该按排序顺序存储在 TreeMap 中，所以我直接将它们取出并将它们插入到整数列表中

public static void verticalNodes(TreeNode root, TreeMap<Integer, Integer> solve, int row, int col) {
    if (root == null) {
        return;
    }
    solve.putIfAbsent(col, root.data);
    verticalNodes(root.left, solve, row + 1, col - 1);
    verticalNodes(root.right, solve, row + 1, col + 1);        
}

并将节点放入顶部视图的整数列表中 -

public static List<Integer> getTopView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    TreeMap<Integer, Integer> solve = new TreeMap<>();
    verticalNodes(root, solve, 0, 0);
    for (int val : solve.values()) {
        ans.add(val);
    }        
    return ans;
}

Answer 1

你的算法不正确。通过深度优先遍历，您不确定是否会在同一列中的任何其他节点之前访问列的顶部节点。

考虑这棵树：

   1
  / \
 2   3
  \
   4
    \
     5

深度优先搜索将首先递归到左分支，直到节点 5，并为第 1 列注册该值。当稍后访问节点 3 时，该值将不会写入您的 TreeMap。

你需要重新考虑这一点。提示：使用广度优先。