如何在二叉树中找到同一级别的两个节点之间的水平距离？

Question

给定一棵二叉树： 高度为 3 的二叉树

我想找到同一级别的两个节点之间的水平距离，同时计算中间不存在的节点，而不计算节点本身，例如

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

节点a和d之间的水平距离为 2。

编辑：

请参阅 a 到 d 之间的距离是在同一级别计算的，不包括 a 或 d 的父节点或子节点，而仅包括同一级别的缺失节点。所以 a 到 d 之间的距离将是 a>(x>y)>d 其中 x 和 y 分别是节点 g 和 h 的缺失子节点。因此，不计算目标节点 a 和 d 的水平距离为 2

Answer 1

可以这样想：

      a
    /   \
   b      c
  /  \   / \
 e    f g   h

现在，您想要确定同一级别的节点之间的水平距离。例如：f 和 g。这是一个逐步的方法：

1. 对二叉树进行层序遍历并将值存储在数组中。
2. 这会产生一个数组，其元素作为节点值。
3. 遍历数组元素。当遇到f（起始节点）时，将计数器设置为0。
4. 继续遍历数组并检查：
   1. 如果g遇到（结束节点），则停止遍历。
   2. 如果计数器已经设置，并且没有遇到结束节点，则将计数器的值更新1。
5. 最后，打印计数器的值。

更新：正如 anand_v.singh 所指出的，如果树可能没有在所有级别上完全填充，那么它可能会产生错误的结果。
为了克服这个问题，tree_height将确定一个称为的附加参数。假设树的高度为3，则数组最多包含2个^tree_height -1元素，所有元素都初始化为不等于任何树节点的值。现在，您可以使用类似于二进制堆的数组表示形式的东西，将节点值放入数组中各自的索引处。然后按照上述步骤即可得到结果。