算法 - O（n）中二进制搜索树的每两个节点之间的距离之和？ [英] Algorithm- Sum of distances between every two nodes of a Binary Search Tree in O(n)?
问题描述
问题是找出BinarySearchTree的每两个节点之间的距离总和，假设每个父子对由单位距离分开。它是在每次插入后计算的。
The question is to find out sum of distances between every two nodes of BinarySearchTree given that every parent-child pair is separated by unit distance. It is to be calculated after every insertion.
ex：
->first node is inserted..
(root)
total sum=0;
->left and right node are inserted
(root)
/ \
(left) (right)
total sum = distance(root,left)+distance(root,right)+distance(left,right);
= 1 + 1 + 2
= 4
and so on.....
我提出的解决方案：
-
蛮力。步骤：
Brute-force. Steps:
- 执行DFS并跟踪所有节点：
O（n）。 - 选择每两个节点并计算：
O（nC2）_times_O（log（n））= O（n2log（n））使用最低共同祖先方法将它们加起来并加起来。
- perform a DFS and track all the nodes :
O(n). - Select every two nodes and calculate :
O(nC2)_times_O(log(n))=O(n2log(n))distance between them using Lowest Common Ancestor Method and add them up.
整体复杂程度： -O（n2log（n））。
O（nlog（n））。步骤： -
- 在插入之前执行DFS并跟踪所有节点：
O（n）。 - 计算插入节点与
O（nlog（n））之间的距离。其余节点。 - 使用步骤2中计算的总和添加现有金额
- Before insertion perform DFS and track all nodes :
O(n). - Calculate distance between the inserted node and :
O(nlog(n)). the remaining nodes. - Add the existing sum with the sum calculated in step 2
总体复杂性： -O（nlog（n））。
现在的问题是是否有任何解决方案存在 O（n） ??
Now the question is "is there any solution exists of order of O(n)??
推荐答案
我们可以通过遍历树两次来做到这一点。
We can do this by traverse the tree two times.
首先，我们需要三个数组
First, we need three array
int [] left ，它存储了左子树距离的总和。
int []left which stored the sum of the distance of the left sub tree.
int [] right ，它存储了右子树距离的总和。
int []right which stored the sum of the distance of the right sub tree.
int [] up ，它存储了父树的距离之和（没有当前的子树）。
int []up which stored the sum of the distance of the parent tree (without the current sub tree).
所以，首先遍历，对于每个节点，我们计算左右距离。如果节点是叶子，只需返回0，如果没有，我们可以有这个公式：
So, first traversal, for each node, we calculate the left and the right distance. If the node is a leaf, simply return 0, if not, we can have this formula:
int cal(Node node){
int left = cal(node.left);
int right = cal(node.right);
left[node.index] = left;
right[node.index] = right;
//Depend on the current node have left or right node, we add 0,1 or 2 to the final result
int add = (node.left != null && node.right != null)? 2 : node.left != null ? 1 : node.right != null ? 1 : 0;
return left + right + add;
}
然后对于第二次遍历，我们需要添加到每个节点，总数与父母的距离。
Then for the second traversal, we need to add to each node, the total distance from his parent.
1
/ \
2 3
/ \
4 5
例如，对于节点1（根），总距离 left [1] + right [1] + 2 ， up [1] = 0 ; （我们添加2，因为根有左右子树，它的确切公式是：
For example, for node 1 (root), the total distance is left[1] + right[1] + 2, up[1] = 0; (we add 2 as the root has both left and right sub tree, the exact formula for it is:
int add = 0;
if (node.left != null)
add++;
if(node.right != null)
add++;
对于节点2，总距离左[2] +右[2] +加+上[1] +右[1] + 1 + addRight ， up [2] = up [1] + right [1] + addRight 。之所以有公式末尾的 1 是因为从当前节点到其父节点有一条边，所以我们需要添加 1 。现在，我表示当前节点的额外距离是 add ，如果父节点中有一个左子树，则需要额外的距离 addLeft 和类似 addRight 用于右子树。
For node 2 , the total distance is left[2] + right[2] + add + up[1] + right[1] + 1 + addRight, up[2] = up[1] + right[1] + addRight. The reason there is a 1 at the end of the formula is because there is an edge from the current node to his parent, so we need to add 1. Now, I denote the additional distance for the current node is add, additional distance if there is a left subtree in parent node is addLeft and similarly addRight for right subtree.
对于节点3，总距离为 up [1] + left [1] + 1 + addLeft ， up [3] = up [1] + left [1] + addLeft ;
For node 3, the total distance is up[1] + left[1] + 1 + addLeft, up[3] = up[1] + left[1] + addLeft;
对于节点4，总距离 up [2] +右[2] + 1 + addRight ， up [4] = up [2] + right [2] + addRight ;
For node 4, the total distance is up[2] + right[2] + 1 + addRight, up[4] = up[2] + right[2] + addRight;
因此，依赖于当前节点是左或右节点，我们相应地更新 up 。
So depend on the current node is a left or right node, we update the up accordingly.
时间复杂度 O（n）
这篇关于算法 - O（n）中二进制搜索树的每两个节点之间的距离之和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
