二叉树在x轴上的最大投影

Question

在坐标平面上给定一棵二叉树，其根节点具有坐标(x,y)。我们需要找到这棵树在x轴上的最大投影。也就是说，基本上我们需要找到这棵树的最大宽度。该树也可能是倾斜的。

示例：

    1
   / \
  2   3
 /   / \
4   5   6

Width = 5

    1
   / \
  2   3
 /  
4   

宽度 = 4

    1
   / 
  2  
 /   
4   

宽度 = 3

我的想法是找到最左边的节点和最右边的节点，然后将它们的x坐标相减。当从根节点向左子树移动时，x变为x-1，y变为y+1，而当向右子树移动时，x变为x+1。找到这两个坐标xLeft和xRight后，我们可以找到最大的宽度。但我在编码时遇到了困难。

有人能告诉我如何解决吗？这不是一个作业问题，但它是我在某个地方读到的编程谜题。

- h4ck3d

---

可能是树形结构可视化算法的重复问题。 - mbeckish

@mbeckish- 我不认为这个问题是重复的。链接的问题是关于如何布置树中的节点。而这个问题是关于发现树的结构属性的一个问题。 - templatetypedef

@templatetypedef - 这两个问题都是关于确定特定树形图形表示的宽度，对吗？如果这不是问题所涉及的内容，那么你对“最大宽度”的定义是什么？ - mbeckish

我认为在额外的编辑之前，@kasavbere已经说得对了。但是你需要告诉我们，你是如何计算 width=5 的？你是说4的x坐标是0，6的x坐标是5吗？因为实际上宽度应该是4，因为2 - -2 = 4。请提供更多细节。 - Konsol Labapen

Answer 1

这是一个层序遍历问题。当您按层顺序遍历树时，跟踪最大级别的宽度。完成后，该级别的最左节点和最右节点将为您提供所需的最终投影。

编辑：

mbeckish：上述解决方案假定问题涉及最大横截面。但如果不是这种情况，则仍然可以使用层序遍历。除了代码必须在遍历期间同时跟踪minX和maxX。minX将跟踪最左节点，而maxX将跟踪最右节点。然后答案将是maxX-minX+1。 此网站有许多经过充分记录的bst遍历代码可供修改。

- kasavbere

---

你的解决方案对于 Op 的第一个示例，Width 是 5 还是 3？ - mbeckish

@mbeckish 很好的发现。我进行了编辑。确实是层序遍历。除了我的原始回答是针对最大横截面的。 - kasavbere

我认为在你修改之前，你已经做得很对了。问题出在 OP 上，它缺少坐标的具体细节。我会要求提供更多细节。 - Konsol Labapen

@kasavbere 我理解这个问题是将节点放置在离散的列和行中（类似于位图或文本行和列的像素），并安排节点使树以漂亮的金字塔形结构排列（每个节点居中于其子树之上）。然后问题就是确定需要多少列来容纳整棵树。 - mbeckish

@templatetypedef 我想我可能一开始误解了问题，但如果mbeckish的评估是正确的，那么我的最新编辑是正确的。代码必须在遍历过程中跟踪到目前为止看到的minX和maxX。根据mbeckish的解释，你的代码似乎也是正确的。 - kasavbere

Answer 2

你可以通过执行标准的树遍历算法，同时保持当前节点的x坐标来解决这个问题。每当你向左走时，你会减少x的值，每当你向右走时，你也会减少x的值。下面是示例代码：

void ExtremalNodes(Node* curr, int x, int& maxX, int& minX) {
    if (curr == nullptr) return;
    maxX = std::max(x, maxX);
    minX = std::min(x, minY);
    ExtremalNodes(curr->left, x - 1, maxX, minX);
    ExtremalNodes(curr->right, x + 1, maxX, minX);
}
int TreeProjection(Node* root) {
    if (root == nullptr) return 0;

    int maxX = 0;
    int minX = 0;
    ExtremalNodes(root, 0, maxX, minX);
    return maxX - minX + 1;
}

希望这能有所帮助！

- templatetypedef

---

你如何知道每个节点的x坐标？从你对ExtremalNodes的递归调用来看，似乎你假设左子节点总是在其父节点的左侧一单位，右子节点总是在父节点的右侧一单位。但这在一般情况下并不成立。例如，在完全二叉树中，根节点的左右子节点将分别被广泛地分开以为它们的宽子树腾出空间。 - mbeckish

@mbeckish- OP明确提到，转到左侧或右侧子节点会将x更改为+/-1，这就是这个答案的来源。我同意这在实践中不起作用，但我认为这更多是一个理论问题。 - templatetypedef