我要招人

去企业版

首页 > 试题广场 >

写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函

[问答题]

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

查看答案及解析

推荐

二三浪迹天涯

//递归式求最大最小值，时间复杂度O(n) 
void findminmax(treenode* tree, int& maxval, int& minval) {
    if (maxval < tree->val) {
        maxval = tree->val;
    }
    if (minval > tree->val) {
        minval = tree->val;
    }
    if (tree->left != NULL)
        findminmax(tree->left, maxval, minval);
    if (tree->right != NULL)
        findminmax(tree->right, maxval, minval);
}

编辑于 2015-02-09 21:08:30 回复(3)

__next__

int diff(Node *root) {
    if (root == NULL)
        return 0;

    int max = root->data, min = root->data;
    queue<Node*> q;
    q.push(root);
    while (! q.empty()) {
        Node *temp = q.front();
        q.pop();
        max = temp->data > max ? temp->data : max;
        min = temp->data < min ? temp->data : min;
        if (temp->left)
            q.push(temp->left);
        if (temp->right)
            q.push(temp->right);
    }
    return max - min;
}

编辑于 2015-04-15 16:26:23 回复(2)

牛在牛客

定义两个参数n_max和n_min，遍历二叉树将节点值与n_max和n_min比较并更新，最后返回n_max-n_min

发表于 2015-05-05 23:17:50 回复(0)

victorisildur

遍历的同时维护最大最小值。
o(n)

发表于 2014-12-11 11:38:20 回复(0)

侯卿

注意看题目，这个树人家没说是排序树！！！

发表于 2018-04-01 22:35:40 回复(0)

sadanahly

//遍历，更新遍历过程中的最小值及最大值，最后求解两者的差值即可。

int getMaxDiff(TreeNode *treeVec){

int minValue = 0, maxValue = 0;

searchTree(treeVec, minValue, maxValue);

return maxValue - minValue;

}

void searchTree(TreeNode *root, int &minValu, int &maxValue){

if(NULL == root)

return;

if(root->val < minValue)

minValue = root->val;

if(root->val > maxValue)

maxValue = root->val;

if(root->left != NULL)

searchTree(root->left, minValue, maxValue);

if(root->right != NULL)

searchTree(root->right, minValue, maxValue);

}

发表于 2016-04-12 16:51:12 回复(0)

我就是你想要的Offer

#include<iostream>
#include<string>
using namespace std;

int main(void)
{
	string query;
	string text;
	cout << "请输入query字符串：";
	cin >> query;
	cout << "请输入text字符串：";
	cin >> text;
	int m = query.size();
	int n = text.size();
	int arr[100][100] = {0};
	for (int i = 0; i < n;i++)
	{
		if (text[i]==query[0])
		{
			arr[0][i] = 1;
		}
	}
	for (int j = 0; j < m;j++)
	{
		if (text[0]==query[j])
		{
			arr[j][0] = 1;
		}
	}
	for (int i = 1; i < m;i++)
	{
		for (int j = 1; j < n;j++)
		{
			if (text[j]==query[i])
			{
				arr[i][j] = arr[i - 1][j - 1] + 1;
			}
		}
	}
	int max = 0;
	int hangbiao = 0;

	for (int i = 0; i < m;i++)
	{
		for (int j = 0; j < n;j++)
		{
			if (arr[i][j]>max)
			{
				max = arr[i][j];
				hangbiao = i-max+1;
			}
		}
	}
	cout << "最大子串长度：" << max << endl << "子串如下：" << endl;
	for (int i = 0; i < max;i++)
	{
		cout << query[hangbiao + i];
	}
	cout << endl;
	system("pause");
	return 0;
}

发表于 2016-04-08 13:24:27 回复(0)

牛客832163号

感觉就是找树里的最大最小数吧

发表于 2016-03-13 22:53:10 回复(0)

张志钢

答案就是经典！

发表于 2015-10-23 00:58:01 回复(0)

谁最牛？

发表于 2015-08-24 11:04:01 回复(0)

Blz.Galaxy

建立二叉查找树，注意去掉值相同的节点，然后分别递归找最左节点与最右节点，作差

发表于 2015-08-22 21:35:59 回复(0)

山大王是我

<div> 假设二叉树用数组来实现，则通过遍历找到最大和最小值，时间复杂度为O(n)，空间复杂度为O(1)，java代码如下： public class BinaryTree {         public static void main(String[] args) {             int[] tree = {1,2,3,-1,9,-1,10,4,5,8};             System.out.println("树中节点最大差值为： " + getMaxGapofNodes(tree));         }         //int[] tree = {1,2,3,-1,9,-1,10,4,5,8}，-1表示该位置无节点         public static int getMaxGapofNodes(int[] tree) {             int result = 0;             int maxindex = 0;             int minindex =0;             //遍历找最大值和最小值             if (tree!=null&&tree.length>0) {                 maxindex = minindex =0;                 for(int i = 1; i<tree.length; i++) {                     if (tree[i] > 0) {                         if (tree[i]>tree[maxindex]) maxindex = i;                         if (tree[i]<tree[minindex]) minindex = i;                     }                 }             }             result = tree[maxindex] - tree[minindex];             return result;         } } </div>

发表于 2015-08-16 18:26:08 回复(0)

kaiseu

<pre class="prettyprint lang-java">class Node{ Node left,right; left = right = null; int data; public Node(int data){ this.data = data;} } public class Main{ public static int maxDistance(Node node){ if(node == null) &nbsp; return 0; &nbsp; if(node.left == null) return maxDistance(node.right); if(node.right == null) return maxDistance(node.left); &nbsp; int max_left,max_right; &nbsp; max_left = Math.abs(node.data,maxDistance(node.left)); &nbsp; max_right = Math.abs(node.data, maxDistance(node.right)); &nbsp; return max(max_left,max_right); } public static int max(int a, int b){ return a &gt; b ?: a , b; } }</pre>

发表于 2015-08-15 10:37:00 回复(0)

bigheary

typedef struct treeNode {

int data;

struct treeNode *lchild, *rchild;

}Tree;

static min, max;

min=max=root.data;// root gotten from input, a tree.

int getDiffValue(Tree *p)

{

if(p == NULL)

return (max-min);

else

{

getDiffValue(root->lchild);

if(min > root.data)

min =root.data;

if(max < root.data)

max = root.data;

getDiffValue(root->rchild);

}

return 0; //this should not be reached!

}

发表于 2015-03-31 20:01:14 回复(0)

notlie

int maxValue(Node* root){
    if(root == NULL) return 0;
    int left = maxValue(root->left());
    int right = maxValue(root->right());
    int max = left>right?left：right;
    return root->value()>max?root->value():max;
}
int minValue(Node* root){
    if(root == NULL) return 32767;
    int left = minValue(root->left());
    int right = minValue(root->right());
    int min = left<right?left：right;
    return root->value()<max?root->value():max;
}

int diff(Node* root){
    return maxValue(root)-minValue(root);
}

发表于 2015-03-30 13:45:08 回复(0)

cyq130

struct node
{
    int value;
    node *left;
    node *right;
};

int find(node *P)
{
    static int min = MIN_INF;
    static int max = MAX_INF;
    if(p->value < min)
         min = p->value;
    if(p->value > max)
         max = p->value;
    if(p->left != NULL)
        find(p->left);  
    if(p->right != NULL)
         find(p->right);
    return max-min;
}

发表于 2015-03-11 22:30:33 回复(1)

Ian

int GetMaxGap(Node *rt) {
 if (*rt == null) {
 return 0;
 }
 int *pmax, *pmin;
 *max = *min = rt -> val;
 updateVal(rt, pmax, pmin);
 return *pmax - *pmin;
}

void UpdateVal(Node *rt, int *pmax, int *pmin) {
 if (*rt == null) {
 return;
 }
 if (*pmax < *rt) {
 *pmax = *rt -> val;
 }
 if (*pmin > *rt) {
 *pmin = *rt -> val;
 }
 updateVal(*rt -> left, pmax, pmin);
 updateVal(*rt -> right, pmax, pmin);
}

发表于 2015-02-26 17:46:42 回复(0)

zwleagle2011

int FIND(TREE* t)

{

static int MAX = t->val;

static int MIN = t->val;

if(t)

{

if (MAX < t->val)

MAX = t->val;

if(MIN > t->val)

MIN = t->val;

FIND(t->left);

FIND(T->right);

}

return MAX - MIN;

}

发表于 2015-01-04 19:24:02 回复(1)

古德拉克

发表于 2014-11-04 09:38:19 回复(0)

实况①

先求每个子树的最大值和最小值,递归实现

发表于 2014-10-25 00:26:02 回复(0)

提交观点

问题信息

阿里巴巴集团树

来自：阿里巴巴2015研发工...

难度：

20条回答 121收藏 12905浏览

写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函

问题信息

热门推荐

相关试题