algorithm - 仅根据前序或后序遍历计算 BST 的内部路径长度

Question

你好 StackOverflow 社区!

我想弄清楚如何计算 BST 的内部路径长度，只给定前序或后序遍历(应该没有太大区别)而不构建树；也就是说，我只想使用上面提到的一种遍历。对于你们中的大多数人来说，这可能是一个简单的答案，但你们可能已经认为我在树木方面还很陌生。

好吧，任何想法都值得赞赏和感谢。

Answer 1

由于它是 BST，我们隐式地具有树的中序遍历(元素的排序列表)。

我们可以通过前序或后序遍历创建一个独特的树Pre 将是 [R，小于 R 的元素列表，大于 R 的元素列表]Post 将是 [小于 R 的元素列表，大于 R 的元素列表，R]

伪代码看起来像这样。

findIPLPreOrder(poArray,startIndex,endIndex, height) {
     if(startIndex==endIndex){
          retrn height;
     }
     m=findIndexOfEndofLeftSubTree(poArray,start,end);
     return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);     
}

findIndexOfEndofLeftSubTree(poArray,start,end){
  R=poArray[start]
  for(i=start+1;i<=end;i++){
     if(R < poArray[i]){
         return i-1;
       }
  }
}