阿里 2014-08-29 校招機(jī)試題 求一個(gè)存放整數(shù)的二叉樹(shù)相差最大的兩節(jié)點(diǎn)差值絕對(duì)值
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-09-18 18:27:49 閱讀次數(shù)：2362次
題目：寫(xiě)一個(gè)函數(shù)，輸入一個(gè)二叉樹(shù)，樹(shù)中每個(gè)節(jié)點(diǎn)存放了一個(gè)整數(shù)值，函數(shù)返回這顆二叉樹(shù)中相差最大的兩個(gè)節(jié)點(diǎn)間的差值絕對(duì)值。請(qǐng)注意程序效率。
如果是數(shù)值之差，感覺(jué)怎么著也得遍歷一遍，直接修改下二叉樹(shù)的基本遍歷代碼就可以。
#include<stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node * left;
struct Node * right;
} BitNode, *BiTree;
/* 求差值的函數(shù)，傳入一個(gè)二叉樹(shù)，其中 *min, *max 初始放 root-data, *value 放差值即要求的值 */
void getValue(BiTree bt, int *min, int *max, int* value) {
if(bt == NULL) return;
if (*min > bt->data) *min = bt->data;
if (*max < bt->data) *max = bt->data;
*value = *max - *min;
getValue(bt->left, min, max, value);
getValue(bt->right, min, max, value);
}
void CreateTree(BiTree *bt, int a[], int len, int index) {
if (index > len - 1) return;
(*bt) = (BiTree) malloc(sizeof(BitNode));
(*bt)->data = a[index];
(*bt)->left = NULL;
(*bt)->right = NULL;
CreateTree(&((*bt)->left), a, len, 2 * index + 1);
CreateTree(&((*bt)->right), a, len, 2 * index + 2);
}
/* 兩個(gè)小測(cè)試 */
int main() {
int arr[] = { 0, 1, -9, 3, 4, 5, 6, 7};
int arr2[] = { 0, 1, -9, 3, 10};
BiTree root, root2;
CreateTree(&root, arr, sizeof(arr) / sizeof(int), 0);
CreateTree(&root2, arr2, sizeof(arr2) / sizeof(int), 0);
int a, max = root->data, min = root->data;
int a2, max2 = root2->data, min2 = root2->data;
getValue(root, &max, &min, &a);
getValue(root2, &max2, &min2, &a2);
printf("%d, %d",a,a2);
return 0;
}
// run result: 16, 19
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
