求二叉树中相差最大的两个节点间的绝对值

题目：写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。

算法思想：通过遍历二叉树求得最大值和最小值。

源代码【完整】：

#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;

}