学步园

/*
39.
网易有道笔试：
(1).
求一个二叉树中任意两个节点间的最大距离，
两个节点的距离的定义是这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是 1，和相邻兄弟节点间的距离是 2，优化时间空间复
杂度。

把最深的左子树距离加上最深的右子树距离就是二叉树中两个节点的最大距离。
*/ 
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;


struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 

//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
}

//最大深度 
int getMaxDepth(BTreeNode *root)
{
	if(root==NULL)
		return 0;
	if(NULL==root->left&&NULL==root->right)
		return 0;
		
	int nLeftDepth=0,nRightDepth=0;
	if(NULL!=root->left)
		nLeftDepth=getMaxDepth(root->left)+1;
	if(NULL!=root->right)
		nRightDepth=getMaxDepth(root->right)+1;
		
	return nRightDepth>=nLeftDepth?nRightDepth:nLeftDepth;
}

//取得最大距离=左最大深度+右最大深度   
int getMaxDistance(BTreeNode *root)
{
	if(NULL==root) 
		return 0;
		
	int nLeftDepth=getMaxDepth(root->left);
	nLeftDepth+=(root->left!=NULL?1:0);
	
	int nRightDepth=getMaxDepth(root->right);
	nRightDepth+=(root->right!=NULL?1:0);
	
	return nLeftDepth+nRightDepth;
}

int main()
{
	/*
		 5
	   4   8
	 7 12 10 	
	*/
	int data[]={5,4,8,7,12,10};
	int len=sizeof(data)/sizeof(int);
	BTreeNode *tree=CreateTree(data,0,len);
	
	int nMaxDis = getMaxDistance(tree);  
    cout <<"11.求二叉树中节点的最大距离："<<nMaxDis<<endl;  
    //4
    
    
    /*
		 5
	   4   8
	 7 12 10 13
	16	
	*/
	int data2[]={5,4,8,7,12,10,13,16};
	int len2=sizeof(data2)/sizeof(int);
	BTreeNode *tree2=CreateTree(data2,0,len2);
	
	int nMaxDis2 = getMaxDistance(tree2);  
    cout <<"11.求二叉树中节点的最大距离："<<nMaxDis2<<endl;  
    //5
	return 0;
}