求二叉樹中相差最大的兩個節點間的絕對值

題目：寫一個函數，輸入一個二叉樹，樹中每個節點存放了一個整數值，函數傳回這棵二叉樹中相差最大的兩個節點間的內插補點絕對值。請注意程式效率。

算法思想：通過周遊二叉樹求得最大值和最小值。

源代碼【完整】：

#include <iostream>

using namespace std;

//節點結構體

typedef struct Node

{

int value;            //值

struct Node* left;    //左兒子

struct Node* right;   //右兒子

}treeNode;

//中序周遊

void displayTree(treeNode* node)

{

if(node == NULL)

return;

//先遞歸周遊左子樹

if (node->left != NULL)

displayTree(node->left);

//列印節點值

cout << node->value << " ";

//遞歸周遊右子樹

if (node->right != NULL)

displayTree(node->right);

}

//把node插入到root為根的樹

void insertNode(treeNode* root, treeNode* node)

{

//被插入的節點值大于根節點,應該插入到右子樹中

if(node->value >= root->value)

{

//如果root節點的右子樹不為空，把node遞歸插入到右子樹

if(root->right != NULL)

{

insertNode(root->right, node);

}

else

{

//如果root節點的右子樹為空，那麼node就是root的右兒子

root->right = node;

}

}

else

{

//如果root節點的左子樹不為空，把node遞歸插入到左子樹

if(root->left != NULL)

{

insertNode(root->left, node);

}

else

{

//如果root節點的左子樹為空，那麼node就是root的左兒子

root->left = node;

}

}

}

void insertValue(treeNode* root, int value)

{

treeNode* child = new treeNode();

child->value = value;

child->left = NULL;

child->right = NULL;

insertNode(root, child);

}

//使用數組中的數建立二叉排序樹

void createTree(treeNode** root, int array[], int size)

{

*root = new treeNode();

//把數組的第一個元素作為根節點

(*root)->value = array[0];

(*root)->left = NULL;

(*root)->right = NULL;

//把每個元素作為節點插入到二叉樹中形成二叉排序樹

for(int i = 1; i < size; i++)

{

treeNode* child = new treeNode();

child->value = array[i];

child->left = NULL;

child->right = NULL;

insertNode(*root, child);

}

}

void findMaxDistance(treeNode* root, int &max, int &min)

{

if(root == NULL)

return;

treeNode* p = root;

max = (max > p->value) ? max : p->value;

min = (min < p->value) ? min : p->value;

if(p->left)

findMaxDistance(p->left, max, min);

if(p->right)

findMaxDistance(p->right, max, min);

}

int main()

{

int array[] = {250,50,8,100,12,141,18,-20,-30};

int size = sizeof(array) / sizeof(array[0]);

//建立二叉樹

treeNode* root = NULL;

createTree(&root, array, size);

//周遊二叉樹

cout << "Binary Tree, left-->middle-->right:" << endl;

displayTree(root);

cout << endl;

int max = root->value;

int min = root->value;

findMaxDistance(root, max, min);

cout << "The max distance is: " << max - min << endl;

system("Pause");

return 0;

}