最近用kindle翻了一下_编程之美_，上面有很多不错的题目。比如写一个程序，让系统任务管理器的CPU使用曲线为50%，进阶是如何让 曲线为正弦曲线[1]。还有，如何实现双线程高效下载[2]。都是比较有意思、实用的例子。
最大距离
现在有一个题:求二叉树中节点的最大距离。这种题目一看感觉就是必须用到递归。_算法导论_上说递归算法可能将问题划分为规模不同的子问题。而寻找最小子问题就是关键。
解法如下:
struct Node
{
struct Node *LNode;
struct Node *RNode;
int LeftMaxLen;
int RightMaxLen;
}
int MaxLen=0;
void FindMax(struct Node *root)
{
if(root==NULL)
return;
if(root->LNode==NULL)
root->LeftMaxLen=0;
if(root->RNode==NULL)
root->RightMaxLen=0;
if(root->LNode!=NULL)
{
FindMax(root->LNode);
}
if(root->RNode!=NULL)
{
FindMax(root->RNode);
}
if(root->LNode!=NULL)
{
int temp=0;
if(root->LNode->LeftMaxLen > root->LNode->RightMaxLen)
temp=root->LNode->LeftMaxLen;
else
temp=root->LNode->RightMaxLen
root->LeftMaxLen=temp+1;
}
if(root->RNode!=NULL)
{
int temp=0;
if(root->RNode->LeftMaxLen > root->RNode->RightMaxLen)
temp=root->RNode->LeftMaxLen;
else
temp=root->RNode->RightMaxLen
root->RightMaxLen=temp+1;
}
if(root->LeftMaxLen + root->RightMaxLen > MaxLen)
{
MaxLen=root->LeftMaxLen + root->RightMaxLen;
}
}这里的最小子问题是root==NULL或者可以看做root->LNode==NULL和root->RNode==NULL。所有的节点都是递归到了这一步得到MaxLen的初始化值。
MaxLen用来实时更新最大距离。
Reference
[1].http://www.cnblogs.com/slysky/archive/2011/11/14/2248102.html
[2].http://blog.chinaunix.net/uid-17102734-id-2830233.html
[3].http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
[4].http://book.douban.com/review/3010762/