二叉树最大距离

最近用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==NULLroot->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/



Previous     Next
tuzhi /
Published under (CC) BY-NC-SA in categories algorithm  tagged with