3

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

例子 ：

    1
   / \
  2   3
 /   / \
4   5   6

Width = 5

    1
   / \
  2   3
 /  
4

Width = 4

    1
   / 
  2  
 /   
4

Width = 3

我的逻辑是基本上找到最左边的节点和最右边的节点并减去它们的 x 坐标。从根到左子树x变为x-1y 变为y+1并且在右子树x变为x+1。找到这两个坐标 xLeft 和 xRight 后，我​​们可以找到最大宽度。但是我在编码时遇到了麻烦。

谁能告诉我该怎么做？这不是一个家庭作业问题，而是我在某处读到的一个编程难题。

4

2 回答 2

1

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

编辑：

mbeckish：上述解决方案假设问题是关于最大横截面的。但如果不是这种情况，级别顺序仍然有效。除了代码必须在遍历期间minX和期间进行跟踪。将跟踪最左边的节点并跟踪最右边的节点。那么答案将是。maxXminXmaxXmaxX-minX+1

该站点有许多文档齐全的 bst 遍历代码，您可以对其进行修改。

于 2013-01-18T15:06:26.017 回答
0

您可以通过执行标准树遍历算法来解决此问题，同时保持当前节点的 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;
}

希望这可以帮助！

于 2013-01-18T17:15:29.070 回答