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

Question

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

我想找出同一水平上两个节点之间的水平距离，也计算不在中间的节点，而不计算节点本身，比如在

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

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

编辑：

请参见，a到d之间的距离是在同一级别上计算的，不包括a或d的父节点或子节点，但只包括同一级别上缺少的节点。所以a到d之间的距离是

Answer 1

Here is the code:

/**
* 
* @author satish hawalppagol
*
*/



public class BinaryTreeTest
{
    public int findDistance(Node root, int n1, int n2) 
    {

    int leftNodeToRootNode = Pathlength(root, n1, "leftNodeToRootNode") - 2;
    int rightNodeToRootNode = Pathlength(root, n2,"rightNodeToRootNode") - 2;
    int lcaData = findLCA(root, n1, n2).data;   //LCA->Lowest Common Ancestor
    int lcaDistance = Pathlength(root, lcaData,"lcaDistance") - 1;
    return (leftNodeToRootNode + rightNodeToRootNode) - 2 * lcaDistance;

    }

    public int Pathlength(Node root, int n1,String callingFrom) 
    {

    if (root != null) 
    {

        int x = 0;

        if("rightNodeToRootNode" == callingFrom)
        {

            if(root.left ==null && root.right ==null)
            {
                //do nothing
            }
            else if(root.left ==null || root.right ==null)
            {
                System.out.println("counting the position where the node is not 
                present is : "   +   root.data);
            }
            if ((root.data == n1) || (x = Pathlength(root.left, 
               n1,"rightNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
               n1,"rightNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }
        if("rightNodeToRootNode" != callingFrom )
        {

            if ((root.data == n1) || (x = Pathlength(root.left, 
            n1,"leftNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
            n1,"leftNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }

        return 0;
    }
    return 0;
}

public Node findLCA(Node root, int n1, int n2) 
{

    if (root != null)
    {

        if (root.data == n1 || root.data == n2) 
        {
            return root;
        }
        Node left = findLCA(root.left, n1, n2);
        Node right = findLCA(root.right, n1, n2);

        if (left != null && right != null)
        {
            return root;
        }
        if (left != null) 
        {
            return left;
        }
        if (right != null)
        {
            return right;
        }
    }
    return null;
}

public static void main(String[] args) throws java.lang.Exception 
{

    Node root = new Node(5);
    root.left = new Node(2);
    root.right = new Node(3);
    /*root.left.right = new Node(12);*/
    root.left.left = new Node(7);
    root.left.left.left = new Node(9);
    /*root.left.left.right = new Node(17);*/

    root.right.right = new Node(1);
    /*root.right.right.left = new Node(4);*/
    root.right.right.right = new Node(6);

    BinaryTreeTest binaryTreeTest = new BinaryTreeTest();
    System.out.println("Distance between 9 and 6 is : " + 
    binaryTreeTest.findDistance(root,9, 6));
    }

}

class Node 
{
int data;
Node left;
Node right;

    public Node(int data) 
    {
    this.data = data;
    this.left = null;
    this.right = null;
    }
}


///////////input/////////   
//          5          //   
//        /    \       //   
//       2     3       //   
//      / \      \     //   
//     7          1    //   
//    /  \       /  \  // 
//   9               6 // 
///////////input/////////   

counting the position where the node is not present is : 2
counting the position where the node is not present is : 7
counting the position where the node is not present is : 3
counting the position where the node is not present is : 1
Distance between 9 and 6 is : 4

Answer 2

就内存而言，这是一种可能不是最佳解决方案的方法。

因此，欢迎提出建议/改进。

算法-

• 使用广度优先搜索（级别顺序）方法遍历BT 遍历时，考虑空白（节点不存在）为“-1”
。
• 在数组中插入BFS路径元素，查找要查找的2个节点元素的索引
• 使用索引计算距离

复杂性-时间：O（N）空间：O（N）

假设-BT中的每个节点都有唯一的值。

class Node {
  Node() {
    value = -1;
  }
  Node(int num) {
    value = num;
  }
  int value;
  Node left = null;
  Node right = null;
}

声明一些必需的DS

static Queue<Node> queue = new LinkedList<Node>();
static ArrayList<Integer> list = new ArrayList<Integer>();
static Set<Integer> set = new HashSet<Integer>();

然后是三个功能

 static void convertBTToArray() {
    if (set.isEmpty())
      return;
 
    Node node = queue.poll();
 
    if (node != null) {
      list.add(node.value);
 
      if (node.value != -1)
        set.remove(node.value);
 
      if (node.left != null) {
        queue.add(node.left);
        set.add(node.left.value);
      } else
        queue.add(new Node());
      if (node.right != null) {
        queue.add(node.right);
        set.add(node.right.value);
      } else
        queue.add(new Node());
 
      convertBTToArray();
 
    } else
      return;
  }
 
 
  static void init(Node root) {
    // traverse in BFS fashion (level order) and convert to Array.
    Node rootCopy = root;
    if (rootCopy != null) {
      queue.add(rootCopy);
      set.add(rootCopy.value);
      convertBTToArray();
    }
  }
 
    // get distance between start and end values.
  static int getHorizontalDistance(int startValue, int endValue) {
    int startIndex = -1, endIndex = -1;
    for (int i = 0; i < list.size(); i++) {
      if (startIndex == -1)
        startIndex = list.get(i) == startValue ? i : -1;
 
      if (list.get(i) == endValue) {
        endIndex = i;
        break;
      }
    }
 
    // check if both numbers are from same level else return -1
    if (Math.floor(Math.log(startIndex + 1) / Math.log(2)) >= 0
      && Math.floor(Math.log(endIndex + 1) / Math.log(2)) >= 0)
      return (endIndex - startIndex - 1);
    else
      return -1;
  }

最后是主要方法

public static void main(String...s) {
    // create your tree and enter elements here

    // -1 indicates that distance cant be found and hence invalid input.
    System.out.println("Dist(7,1): "+getHorizontalDistance(7, 1));
    
  }

Answer 3

这样想：

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

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

1. 执行二叉树的级别顺序遍历，并将值存储在数组中

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