让我非常清楚,我没有了解水平距离是什么。
但还是从我的角度来看。水平距离是指:同一级别的给定节点之间缺少或存在的节点。
在我的例子中,当我试图找出 7
和 1
之间的距离时,我得到的输出是 2。这就是为什么我会按照上面提到的方式思考。
但是如果我试图找出 9
和 6
之间的距离,我得到的输出是 4。
例如,在给定的树中,同一级别的节点 7 和 1 之间的距离为 2 (考虑节点2的右 child 和节点3的左 child )
下面是我用来检查距离的代码。
public class BinaryHorizontalDistance
{
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.right = new Node(2);
root.left = new Node(3);
root.right.right = new Node(7);
//root.right.left = new Node(78);
root.right.right.right = new Node(9);
root.left.left = new Node(1);
//root.left.right = new Node(22);
root.left.left.right = new Node(4);
root.left.left.left = new Node(6);
BinaryHorizontalDistance binaryTreeTest = new BinaryHorizontalDistance();
System.out.println("Distance between 7 and 1 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;
}
}
如能提供示例说明,我们将不胜感激。并乐于进一步解释
最佳答案
你知道定义:
- 如果你是左 child :计数-1,
- 如果你是对的 child :数+1
5
/ \
4 6
在这里,计算h(4,6)
- 4 是 5 的左 child :-1
- 6 是 5 的右 child :+1
h(4,6) = 0
5
/ \
4 6
\
2
在这里,为了计算 h(2,6)
,2
是 4 的右 child (** 显然 如果节点是独生子,则必须将其视为右 child ):
所以 h(2,4)=+1
回想一下
h(4,6)=0
所以 h(2,6) = 1
关于你的一个例子,说h(9,6)
h(9,7) = 2
h(2,3) = 0
h(3,1) = 1 (1 only child so +1)
h(1,6) = 1 (same)
total: 4
** 我想选择 +1 是为了保持一致性,但我只是观察到了它
关于java - 给定一棵二叉树,找出同一层的2个节点之间的水平距离,同时计算该节点不存在的位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58456540/