求二叉樹最大葉子節點距離(不含全局變量)

題目: 輸入一顆二叉樹先序周遊的字元串，輸出該二叉樹的最大葉子節點距離

分析知，最大的距離要麼是經過根節點的一條路徑，要麼是在左子樹中的一條路徑，或者是在右子樹中的一條路徑。

那麼可以知道最大葉子節點的距離是左右子樹的高度和、左子樹最大葉節點距離、右子樹最大葉節點距離中的最大值。

可以摒棄前面的用全局變量記錄最大葉節點距離的方法(不可重入)，代碼如下。

#include<iostream>
using namespace std;
//樹節點類型定義
struct BTNode
{
	char value;
	BTNode* left;
	BTNode* right;
	BTNode(char k):value(k),left(NULL),right(NULL){}
};

//三個數中取最大值
int Max(int a,int b,int c)
{
	int tmp = a>b?a:b;
	return tmp>c?tmp:c;
}

//求樹的高度
int TreeHeight(BTNode* root)
{
	if(root == NULL)
		return -1;
	int ldepth = TreeHeight(root->left);
	int rdepth = TreeHeight(root->right);
	return ldepth>rdepth?ldepth+1:rdepth+1;
}

//求經過根節點的最大兩個節點的距離
int LenViaRoot(BTNode* root)
{
	if(root == NULL)
		return 0;
	int leftLen  = TreeHeight(root->left);
	int rightLen = TreeHeight(root->right);
	return leftLen + rightLen + 2;
}

//主調函數，求二叉樹中兩個葉節點的最大距離
int maxLeafLen(BTNode* root)
{
	if(root == NULL)
		return 0;
	return Max(LenViaRoot(root),maxLeafLen(root->left),maxLeafLen(root->right));
}

//按先序周遊的順序輸入字元串構造一顆二叉樹
void createBTree(BTNode*& root)
{
	char val = getchar();
	if(val == '#')
	{
		root = NULL;
		return;
	}
	else
	{
		root = new BTNode(val);
		createBTree(root->left);
		createBTree(root->right);
	}
}

//後序周遊的方式輸出二叉樹以驗證上面的先序周遊順序建立的二叉樹的正确性
void postOrderRecursive(BTNode* root)
{
	if(root != NULL)
	{
		postOrderRecursive(root->left);
		postOrderRecursive(root->right);
		cout<<root->value<<" ";
	}
}


int main()
{
	BTNode* root = NULL;
	cout<<"請按先序周遊的方式輸入一顆二叉樹節點序列，#代表空節點: ";
	createBTree(root);
	cout<<"構造的二叉樹的後序周遊為: ";
	postOrderRecursive(root);
	cout<<endl;
	cout<<"二叉樹中最大葉節點距離: "<<maxLeafLen(root)<<endl;
	return 0;
}