算法 - 二叉搜索树每两个节点之间的距离总和，时间复杂度为 O(n)？

问题是在给定每个父子对间隔单位距离的情况下，找出 BinarySearchTree 中每两个节点之间的距离之和。每次插入后都要计算它。

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.....

我想出的解决方案：

1. 蛮力。脚步：

   1. 执行 DFS 并跟踪所有节点：O(n).
   2. 选择每两个节点并计算：O(nC2)_times_O(log(n))=O(n2log(n))他们之间的距离使用最低共同祖先 http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/方法并将它们相加。

   总体复杂性：-O(n2log(n)).

2. O(nlog(n))。脚步：-

   1. 在插入之前执行 DFS 并跟踪所有节点：O(n).
   2. 计算插入节点 与 之间的距离：O(nlog(n))。其余节点。
   3. 将现有总和与步骤 2 中计算的总和相加

   总体复杂性：-O(nlog(n)).

现在的问题是“是否存在以下顺序的解决方案：O(n)??

我们可以通过遍历树两次来做到这一点。

首先我们需要三个数组

int []left它存储左子树的距离之和。

int []right它存储了右子树的距离之和。

int []up它存储父树（没有当前子树）的距离总和。

所以，首先遍历，对于每个节点，我们计算左右距离。如果节点是叶子，则简单地返回0，如果不是，我们可以有这个公式：

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;
}

然后，对于第二次遍历，我们需要向每个节点添加距其父节点的总距离。

             1
            / \
           2   3
          / \
         4   5

例如，对于节点 1（根），总距离为left[1] + right[1] + 2, up[1] = 0; （我们加2是因为根有左子树和右子树，它的确切公式是：

int add = 0; 
if (node.left != null) 
    add++;
if(node.right != null)
    add++;

对于节点 2 ，总距离为left[2] + right[2] + add + up[1] + right[1] + 1 + addRight, up[2] = up[1] + right[1] + addRight。原因有一个1公式最后是因为当前节点到他的父节点有一条边，所以我们需要添加1。现在，我表示当前节点的附加距离是add，如果父节点有左子树，附加距离为addLeft和类似地addRight为右子树。

对于节点 3，总距离为up[1] + left[1] + 1 + addLeft, up[3] = up[1] + left[1] + addLeft;

对于节点 4，总距离为up[2] + right[2] + 1 + addRight, up[4] = up[2] + right[2] + addRight;

所以根据当前节点是左节点还是右节点，我们更新up因此。

时间复杂度为O(n)