2010年11月21日微软实习生笔试题--反序对 数目求解

题目大意：输入n个正整数（<=2,000,000),计算其中的反序对的个数。例如5,4,3,2,1的反序对数是4对，1,2,3,4,5的反序对数是0。（注意是相邻的逆序，不统计不相邻的逆序，当时搞错了，太冤了，但大概思想是对的。 后来经下面的哥们提醒，确实如果只是相邻的只要O（n）就能解决了，不需要O(nlogn)。那么推理原来的思想是对的，也就是统计所有的，5，4，3，2，1应该是10对。总之给出了两种情况的二叉树方法）
解决方法:1）将输入的数字按输入的顺序建立二叉排序树，（如果大于或等于该节点，则比较它的右子树；如果小于则比较它的左子树。当比较到空节点时，则插入这个节点）。
2）计算反序对数，遍历树的每个节点，如果该节点没有左子树则反序对为0，往其右子树遍历。如果该节点右左子树，则统计其左子树上的所有节点的个数。 递归的临界条件是：当前结点的左右结点都为空，返回0。

当时的想法是对的，程序也编的差不多。今天实际在机子上编写，发现原来的纸上的程序还是有很多问题的。（今天也弄了将近一个小时）
昨天的问题：1）没有Public，
2）template针对Class变量的使用错误，建立是需要TreeNode * root=new TreeNode(); 即在类名后面加上类型。 函数传递时也需要将TreeNodeT变量加入。
3)递归的时候在只需要一个函数就可以了，临界条件是对的，但是当右子树时
if(pTree->rightchild!=NULL) //注意是if，不是while，因为已经递归的计算了
{
return CaculateReversePairs(pTree->rightchild);//右子树，不能加1
}
不需要加1，当时可能没哟加1，但是印象中又好像加了，这一点非常重要。

#ifndef REVERSE_PAIRS_H
#define REVERSE_PAIRS_H
template<class T>
struct Node{
	T key;
};
template<class T>
class TreeNode{
public:
	TreeNode<T> * leftchild;
	TreeNode<T> * rightchild;
	Node<T> data;
	TreeNode(){
		leftchild=NULL;
		rightchild=NULL;
	}
    ~TreeNode();
};
#endif

############.cpp#######################

// ReverseOrder.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "ReversePairs.h"
#include <iostream>
using namespace std;
template<class T>
void InsertTreeNode(T dataIn,TreeNode<T> * root) //not include the first one(root)
{
  TreeNode<T> * pTree=root;
  TreeNode<T> * pTreeStored=pTree;
  TreeNode<T> * newNode=new TreeNode<T>();
  newNode->data.key=dataIn;
   while(pTree!=NULL)
   {
	   if(dataIn>=pTree->data.key)
	   {
		   pTreeStored=pTree;
		   pTree=pTree->rightchild;
	   }
	   else
	   {
		   pTreeStored=pTree;
		   pTree=pTree->leftchild;
	   }
   }
   if(dataIn>=pTreeStored->data.key)
   {
	   pTreeStored->rightchild=newNode;
   }
   else
   {
	   pTreeStored->leftchild=newNode;
   }
}
template<class T>
int CaculateReversePairs(TreeNode<T> * pTree) //递归地计算,中序遍历的思想
{
	int result=0;
	if(pTree->leftchild==NULL && pTree->rightchild==NULL)
		return 0;
//	while(pTree->leftchild!=NULL)
	if(pTree->leftchild!=NULL)  //注意是if不是while，因为递归地运算了。
	{
		result+= CaculateReversePairs(pTree->leftchild)+1;
	}
//	while(pTree->rightchild!=NULL)
	if(pTree->rightchild!=NULL)
	{
		result+= CaculateReversePairs(pTree->rightchild);//右子树，不能加1
	}
	return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	long a[100];
	cout<<"Input the number of integers:/n";
	cin>>n;
	TreeNode<long> * root=new TreeNode<long>();
	for(int i=0;i<n;i++)
	{
	cin>>a[i];	
	}
	root->data.key=a[0];
	for(int i=1;i<n;i++)
	{
		InsertTreeNode(a[i],root);
	}
	cout<<"The ReverseOrderPairs number is:/n";
	cout<<CaculateReversePairs(root)<<"/n";
	system("pause");
	return 0;
}

二、如果按照我的思想，即每个节点都要统计左子树所有节点数目。例如5,4,3,2,1逆序数为10，（5.4）……（5,1）；（4，3）……（4,1）；……（2,1）
这就需要在每次访问该节点时统计该节点左子树的所有节点数目。并且按这种方式中序遍历树中的所有节点。

template<class T>
int CaculateSubTreeNodes(TreeNode<T> * pTree) //中序遍历子树的所有节点个数
{
	int result=0;
	if(pTree->leftchild==NULL && pTree->rightchild==NULL)
		return 1; //当前节点也算一个
	if(pTree->leftchild!=NULL)
		result+=CaculateSubTreeNodes(pTree->leftchild)+1;
	if(pTree->rightchild!=NULL)
		result+=CaculateSubTreeNodes(pTree->rightchild)+1;
	return result;
}
template<class T>
int CaculateReversePairs(TreeNode<T> * pTree) //递归地计算,中序遍历的思想
{
	int result=0;
	if(pTree->leftchild==NULL && pTree->rightchild==NULL)
		return 0;
//	while(pTree->leftchild!=NULL)
	if(pTree->leftchild!=NULL)  //注意是if不是while，因为递归地运算了。
	{
		//result+= CaculateReversePairs(pTree->leftchild)+1;
		result+=CaculateSubTreeNodes(pTree->leftchild); //计算当前节点左子树的所有节点数
		result+= CaculateReversePairs(pTree->leftchild); //遍历左子树
	}
//	while(pTree->rightchild!=NULL)
	if(pTree->rightchild!=NULL)
	{
		result+= CaculateReversePairs(pTree->rightchild);//遍历右子树
	}
	return result;
}