二叉树的底视图

当从底部观察二叉树时可见的节点被称为树的“底部视图”。换句话说，它涉及到找到并显示在考虑每个节点的水平距离和深度的情况下，在树的最低级别上显示的节点。

为了获得二叉树的底部视图，会考虑每个节点相对于根的水平距离 (HD)。根的水平距离被视为 0，当我们向左或向右移动时，水平距离会减少 1 或增加 1。

找到底部视图的基本策略包括以深度优先的方式遍历树，记录每个节点的水平距离，并存储每个水平距离的节点。最终，在确定底部视图时，会考虑每个水平距离上深度最大的节点——在该水平距离上遇到的最后一个节点。

以下是查找二叉树底部视图的分步过程

1. 在以深度优先的方式遍历树时，跟踪每个节点的水平距离和深度。
2. 维护一个映射或数组，用于存储每个水平距离的节点，同时考虑在该距离可达到的最深点。
3. 在遍历树时，更新映射，同时保留每个水平距离上具有最大深度的节点。
4. 在遍历之后，树的底部视图将由每个特定水平距离上的节点组成。

重要的是要记住，该算法的具体实现可能会因所使用的特定编程语言和数据结构而异。

算法中二叉树的底部视图

以二叉树的根作为输入

1. 创建一个映射，以存储底部视图中的节点及其深度和水平距离。

2. 以深度优先的方式遍历二叉树。

- 对于每个节点，将其值和深度添加到映射中，以表示相关的水平距离。

- 增加和减少遍历过程中遇到的水平距离。

3. 遍历映射以获取底部视图节点时，选择映射中深度最大的节点。

4. 显示底部视图中的节点。

伪代码

1. 使用底部视图 (root) 过程，创建一个空的映射来存储底部视图的节点。bottomTraverseTree ViewMap(root, 0, 0, bottomViewMap)

DisplayBottomView(bottomViewMap)

2. Node, horizontal_distance, depth, bottomViewMap; procedure TraverseTree

如果节点为空，则返回

其中 horizontal_distance 不在 bottom depth 中，或者 ViewMap 必须大于 bottomViewMap[horizontal_distance].depth: bottom(Node. value, depth) ViewMap[horizontal_distance]

Node.left, horizontal_distance - 1, depth + 1, bottomViewMap; TraverseTree

Node.right, horizontal_distance + 1, depth + 1, bottomViewMap; TraverseTree

3. DisplayBottomView(bottomViewMap) procedure

对于 items in sorted(bottomViewMap)，按水平距离对 bottomViewMap 进行排序

Present entry.value

用途

为了检索和显示二叉树的底部视图，请使用二叉树的根调用 bottom view (root)。

代码