如何在二叉树中找到同一级别的两个节点之间的水平距离? [英] how to find the horizontal distance between two nodes at the same level in a binary tree?

问题描述

给出一个二叉树:身高为3的二叉树

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

I want to find the horizontal distance between two nodes at the same level also counting the nodes that are not there in between while not counting the nodes themselves, Say in

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

在节点 a 和 d 之间的

水平距离为2.

in between the nodes a and d there is a horizontal distance of 2.

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

Please see distance between a to d is calculated on the same level not including the parent or child nodes of either a or d but only the missing nodes at the same level. so distance between a to d would be a>(x>y)>d where in x and y are the missing child nodes of node g and h respectively. Hence not counting the target nodes a and d there'll be a horizontal distance of 2

推荐答案

这样想:

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

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

Now, you want to determine horizontal distance between nodes at the same level. Eg: f and g. Here is a step by step approach:

1. 执行二叉树的级别顺序遍历，并将值存储在数组中.
2. 这将导致一个数组，其元素为节点值.
3. 遍历数组元素.当遇到 f (起始节点)时，将counter设置为0.
4. 继续遍历数组并检查:

1. Perform a level order traversal of the binary tree and store the values in an array.
2. This results in an array with its elements as node values.
3. Traverse the array elements. When you encounter f (starting node), set counter to 0.
4. Keep traversing the array and check that:

1. 如果遇到 g (结束节点)，则停止遍历.
2. 如果已设置计数器，但未遇到末端节点，则将计数器的值更新为1.

1. If the g (end node) is encountered, then stop traversing.
2. If the counter has been set, and the end node is not encountered, then update the value of the counter by 1.

最后，打印计数器的值.

更新:正如anand_v.singh指出的那样，如果树不可能在所有级别上都被完全填充，那么它将产生错误的结果.
为克服此问题，将确定一个名为 tree_height 的附加参数.假设树的高度为3，则该数组最多包含2个 ^tree_height -1元素，所有元素都初始化为一个不等于任何树节点值的值.现在，您可以使用诸如二进制堆的数组表示之类的方法，将节点值放在它们各自的索引处.然后按照上述步骤获得结果.

Update: As pointed out by anand_v.singh, if the tree might not be completely filled at all levels, then it can produce wrong results.
To overcome this problem, an additional parameter called tree_height will be determined. Suppose, the height of the tree was 3, then the array will contain at most 2^tree_height -1 elements, all initialized to a value that is not equal to the value of any tree nodes. Now, you can use something like array representation of binary heap, to place node values into the array, at their respective indices. Then follow the above-mentioned procedure to obtain the results.

这篇关于如何在二叉树中找到同一级别的两个节点之间的水平距离?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！