【点滴学習-データ構造-二叉樹】二叉樹の二つのノード間の最大距離を求めます.

/*
 *1.        。 
 */	
struct NODE
	{
	     NODE* pLeft;        	//    
	     NODE* pRight;      	//    
	     int nMaxLeft;      	//          
	     int nMaxRight;     	//          
	     char chValue;    	//      
	};
	
	int nMaxLen = 0;
	
	//            
	void FindMaxLen(NODE* pRoot)
	{
	     //        ，  
	     if(pRoot == NULL)
	     {
	          return;
	     }
	
	     //        ，             0
	     if(pRoot -> pLeft == NULL)
	     {
	          pRoot -> nMaxLeft = 0; 
	     }
	
	     //        ，             0
	     if(pRoot -> pRight == NULL)
	     {
	          pRoot -> nMaxRight = 0;
	     }
	
	     //         ，           
	     if(pRoot -> pLeft != NULL)
	     {
	          FindMaxLen(pRoot -> pLeft);
	     }
	
	     //         ，           
	     if(pRoot -> pRight != NULL)
	     {
	          FindMaxLen(pRoot -> pRight);
	     }
	
	     //            
	     if(pRoot -> pLeft != NULL)
	     {
	          int nTempMax = 0;
	          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
	          {
	               nTempMax = pRoot -> pLeft -> nMaxLeft;
	          }
	          else
	          {
	               nTempMax = pRoot -> pLeft -> nMaxRight;
	          }
	          pRoot -> nMaxLeft = nTempMax + 1;
	     }
	
	     //            
	     if(pRoot -> pRight != NULL)
	     {
	          int nTempMax = 0;
	          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
	          {
	               nTempMax = pRoot -> pRight -> nMaxLeft;
	          }
	          else
	          {
	               nTempMax = pRoot -> pRight -> nMaxRight;
	          }
	          pRoot -> nMaxRight = nTempMax + 1;
	     }
	
	     //       
	     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
	     {
	          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
	     }
	}

//    2
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LEAF -1

typedef struct BTreeNode{
     BTreeNode* lchild;
     BTreeNode* rchild;
     int value;

}BTreeNode,*Btree;

BTreeNode* createTree(){
     BTreeNode* T;
     int t;
     scanf("%d",&t);
     if(t == LEAF){
          T = NULL;
     }else{
          T = (BTreeNode *) malloc(sizeof(BTreeNode));
          T->value = t;
          T->lchild = createTree();
          T->rchild = createTree();
     }
     return T;
}

int max(int a,int b){
	return a > b ? a : b;
}

int findMaxLen(BTreeNode* root,int &depth){
    if(root == NULL){
		depth = 0;
		return 0;
	}
    int leftLen = 0,rightLen = 0,maxLeft = 0,maxRight = 0;

	if(root->lchild != NULL){
		maxLeft = findMaxLen(root->lchild,leftLen);
	}
	if(root->rchild != NULL){
		maxRight = findMaxLen(root->rchild,rightLen);
	}
	depth = max(leftLen,rightLen) + 1;
        return max(maxLeft,max(maxRight,leftLen + rightLen));

}


main(){
    BTreeNode * root;
    root = createTree();
	int depth = 0,maxLen = 0;
    maxLen = findMaxLen(root,depth);
    printf("%d 
",maxLen);
    system("pause");
    return 0;
}

//  ：http://www.cnblogs.com/miloyip/archive/2010/02/25/binary_tree_distance.html
//  3
using namespace std;

struct NODE
{
	NODE *pLeft;
	NODE *pRight;
};

struct RESULT
{
	int nMaxDistance;
	int nMaxDepth;
};

RESULT GetMaximumDistance(NODE* root)
{
	if (!root)
	{
		RESULT empty = { 0, -1 };	// trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero.
		return empty;
	}

	RESULT lhs = GetMaximumDistance(root->pLeft);
	RESULT rhs = GetMaximumDistance(root->pRight);

	RESULT result;
	result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1);
	result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2);
	return result;
}