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

Question

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

例子:

    1
   / \
  2   3
 /   / \
4   5   6

宽度 = 5

    1
   / \
  2   3
 /  
4   

宽度 = 4

    1
   / 
  2  
 /   
4   

宽度 = 3

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

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

Answer 1

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

编辑:

mbeckish:上述解决方案假定问题是关于最大横截面的。但如果不是这种情况，水平顺序仍然有效。除了代码必须在遍历期间同时跟踪 minX 和 maxX 之外。 minX 会跟踪最左边的节点，maxX 会跟踪最右边的节点。那么答案就是maxX-minX+1。

This site有许多文档完善的 bst 遍历代码，您可以修改。