首页 > 试题广场 >

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

[问答题]

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

查看答案及解析

推荐

吾落凡

int FindMaxSubMin(BinTree *root) 
{
    stack<BinTree*> s;
    BinTree *p=root;
    int MaxNode = p->data;
    int MinNode = p->data;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            if(p->data > MaxNode)
            {
                MaxNode = p->data;
            }
            if(p->data < MinNode)
            {
                MinNode = p->data;
            }
            s.pop();
            p=p->rchild;
        }
 } 
 return abs(MaxNode - MinNode); 
 }

编辑于 2015-01-31 12:06:29 回复(0)

香蕉牛奶

typedef struct node
{
    int data;
    struct node *plChild;
    struct node *prChild;
}*BiTreePtr;
int find_max_diff(node *root)
{
    static int min = MAX_INF;//初始化为一个足够大的值
    static int max = MIN_INF;//初始化为一个足够小的值
    if (root->data < min)
        min = root->data;
    if (root->data > max)
        max = root->data;
    if (root->plChild != NULL)
        find_max_diff(root->plChild);
    if (root->prChild!= NULL)
        find_max_diff(root->prChild);
    return max - min;
}

编辑于 2015-01-31 12:06:04 回复(2)

峰风

#include<iostream>
#include<string>
#include <vector>
#include <queue>
using namespace std;
struct  NODE
{
	int  data;
	NODE *left;
	NODE *right;
}node;
//首先广度优先遍历一棵树，将值放入一个容器，然后对容器中的数遍历一次获取最大值和最小值
int find(NODE* list)
{
	vector<int> v;
	queue<NODE*> q;
	NODE* p;
	if (NULL==list)
	{
		return 0;
	}
	q.push(list);
	while (!q.empty())
	{
		p = q.front();
		if (p->left!=NULL)
		{
			q.push(p->left);
		}
		if (p->right!=NULL)
		{
			q.push(p->right);
		}
		q.pop();
		v.push_back(p->data);
	}
	
	int mi=v.front();
	int ma=v.front();
	for (int i = 0;i < v.size();i++)
	{
		if (v[i]<mi)
		{
			mi = v[i];
		}
		if (v[i]>ma)
		{
			ma=v[i];
		}
	}
	return (ma-mi);
}

发表于 2015-08-14 17:03:09 回复(0)

希荷

    static int min = 0;     static int max = 0;     public static int findMaxSubM(TreeNode root){         if(root==null){             return 0;         }         min = root.val;         max = root.val;         inOrder(root);         System.out.println(" main===min= " + min + " max= " + max);         return Math.abs(max-min);     }          public static void inOrder(TreeNode node){         if(node==null){             return;         }         min = Math.min(min, node.val);         max = Math.max(max, node.val);         System.out.println(" min= " + min + " max= " + max);         if(node.left!=null){             inOrder(node.left);         }         if(node.right!=null){             inOrder(node.right);         }     }

发表于 2018-03-09 16:52:50 回复(0)

丕子李

<pre class="prettyprint lang-java">public int getValue(TreeNode root) { int []values=findMaxAndMin(root); return Math.abs(values[1]-values[0]); } public int[] findMaxAndMin(TreeNode root) { int r[]=new int[2]; if(root==null) { r[1]=Integer.MAX_VALUE; r[0]=Integer.MIN_VALUE; return r; }; int val=root.val; int left[]=findMaxAndMin(root.left); int right[]=findMaxAndMin(root.right); r[0]=getMax(left[0], right[0], val); r[1]=getMin(left[1], right[1], val); return r; } public int getMax(int a,int b,int c) { if(a>=b&&a>=c) return a; if(b>=a&&b>=c) return b; return c; } public int getMin(int a,int b,int c) { if(a<=b&&a<=c) return a; if(b<=a&&b<=c) return b; return c; }</pre>

发表于 2015-08-21 15:33:37 回复(0)

Royal_Highness

<pre class="prettyprint lang-java">public class btreeNode{ public int val; public btreeNode leftChird = null; public btreeNode rightChild = null; public btreeNode(int val){ this.val = val; } } public void addNode(btreeNode head ,int val){ if(val<head.val){ if(head.leftChird == null){ head.leftChird == new btreeNode(val); }else{ addNode(head.leftChird ,val); }else if(val>head.val){ if(head.rightChird == null){ head.rightChird == new btreeNode(val); }else{ addNode(head.rightChird,val); } } } public int distance(int[] arrs){ if(arrs.length == 0) return 0; if(arrs.length > 0){ btreeNode head = new btreeNode(arrs(0)); for(int i=0;i<arrs.length;i++){ addNode(head,arrs(i)); } } int ptr = head; while(ptr.leftChird!=null) ptr = ptr.leftChird; minVal = ptr.val; ptr = head; while(ptr.leftChird!=null) ptr=ptr.leftChird; maxVal = ptr.val; return maxVal-minVal; } </pre>

发表于 2015-08-21 10:42:38 回复(0)

nailperry

解题思路：

将问题转化为求无序数组中的最大值和最小值，只需在遍历二叉树的过程中分别记住最大值和最小值即可。遍历算法建议用中序遍历的非递归算法，可在O(n)内解决。

编辑于 2015-08-20 21:29:07 回复(0)

叮不隆冬

<div> 算法思想：     1、初始化一个栈，     2、将二叉树的元素依次压入到栈中，初始化最大值max和最小值min为根元素     3、出栈的元素依次与max和min比较     4、result=max-min </div>

发表于 2015-08-20 21:21:34 回复(0)

lp48280421

struct TreeNode 
{ 
                        int val; 
             TreeNode* left;
             TreeNode* right; 
}; 
int maxDiffValue(TreeNode* pRoot)
 {
             if(pRoot==nullptr) 
            { 
                      return 0;
            } 
           int min=pRoot->val; 
           int max=pRoot->val; 
           maxDiffValueCore（pRoot,max,min);
           return (max-min);
 } 
void maxDiffValueCore（TreeNode* pRoot,int&  max,int&  min) 
{
 if(pRoot==nullptr) 
{ 
           return; 
} 
if(pRoot->val>max) 
max=pRoot->val;
 if(pRoot->val<min) 
min=pRoot->val; 
maxDiffValueCore（pRoot->left,max,min); 
maxDiffValueCore（pRoot->right,max,min);
 }

发表于 2015-08-19 22:01:03 回复(0)

小强就是我

<pre class="prettyprint lang-java">public int askMin(TreeNode a){ ArrayList<int> list = new ArrayList<int>(); Stack<TreeNode> mStack = new Stack<TreeNode>(); mStack.push(A); while(mStack.size!=0){ TreeNode tmp = mStack.pop(); list.add(tmp.value); if(p.right!=null){ mStack.push(p.right); } if(p.left!=null){ mStack.push(p.left) } } if(a[0]>a[1]){ int min = a[1]; int max = a[0]; }else{ int min = a[0]; int max = a[1]; } for(int i = 2; i<list.size(); i++){ if(min > a[i]){ min = a[i]; }else if(max < a[i]){ max = a[i]; } } return max -min; }</pre>

发表于 2015-08-18 09:24:01 回复(0)

山大王是我

<div> 遍历二叉树，找出最大和最小值。如果二叉树采用数组实现，则JAVA代码如下，其时间复杂度为O(n)，空间复杂度为O(1)。 public class BinaryTree {     public static void main(String[] args) {         int[] tree = {1,2,3,-1,5,7,-1,10,19};//用数组实现二叉树，其中-1表示该位置没有节点         System.out.println("最大差值是：" + getMaxGap(tree));     }     public static int getMaxGap(int[] tree) {         int result = 0;         int maxindex = 0;         int minindex = 0;         if(tree != null && tree.length > 1) {             for(int i = 1; i < tree.length; i++) {                 if(tree[i] > tree[maxindex]) maxindex = i;                 if(tree[i] < tree[minindex]) minindex = i;             }         }         result = tree[maxindex] - tree[minindex];         return result;     } } </div>

发表于 2015-08-17 10:56:09 回复(0)

ghostman

<pre class="prettyprint lang-cpp">#define MAX_TREE_SIZE 100 typedef struct BiTNode { int m_nValue; struct BiTNode* m_pLChild;   struct BiTNode* m_pRChild; } BiTNode; bool g_InvalidInput = false; int MaxDiffOfNodes(BiTNode* pRoot) {   int ret = 0;   g_InvalidInput = true; if( NULL != pRoot ) { BiTNode* queue[MAX_TREE_SIZE]; int front = 0; int rear = 0; int max = 0x80000000; int min = 0x7FFFFFFF; BiTNode* pNode = NULL; queue[rear++] = pRoot; while( front != rear ) { pNode = queue[front++]; if( pNode->m_nValue > max ) { max = pNode->m_nValue; } if( pNode->m_nValue < min ) { min = pNode->m_nValue; } if( NULL != pNode->m_pLChild ) { queue[rear++] = pNode->m_pLChild; } if( NULL != pNode->m_pRChild ) { queue[rear++] = pNode->m_RLChild; } } ret = max - min; g_InvalidInput = false; } return ret; }</pre>

发表于 2015-08-16 12:53:47 回复(0)

宋常华

<pre class="prettyprint lang-java"> </pre> public class FindTreeMax {         static int max = -99999999;     static int min = 999999999;         public static void getMax(Node head){         if(head!=null){             max = head.value > max ? head.value : max;             min = head.value < min ? head.value : min;             getMax(head.left);             getMax(head.right);         }     } } class Node {     public int value;     public Node left;     public Node right;     public Node(int data) {         this.value = data;     } }

发表于 2015-08-15 22:16:48 回复(0)

pipi

<pre class="prettyprint lang-java">public static long getMaxAbs(TreeNode root){ getMaxAbsHelper(root,Integer.MIN_VALUE,Integer.MAX_VALUE); }</pre> <pre class="prettyprint lang-java"> public static long getMaxAbsHelper(TreeNode root,int max,int min){ if(root == null){ return 0; } if(root.val&gt;max){ max = root.val; } if(root.val &lt; min){ min = root.val; } if(root.left != null){ getMaxAbsHelper(root.left,max,min); } if(root.right != null){ getMaxAbsHelper(root.right,max,min); } return (max-min); }</pre>

发表于 2015-08-14 20:59:53 回复(0)

supen

int FindMaxSub(TreeNode*root)

{

int MinMax[2]={0};

//遍历二叉树，并和已保存的目前最大值最小值比较，比最小值小则替换MinMax[0]，

//比最大值大则替换MinMax[1];

if(root==NULL)

return (MinMax[1]-MinMax[0]);

stack<TreeNode*> stack1;

stack1.push(root);

MinMax[0]=root->val;

while (!stack1.empty())

{

TreeNode* temp=stack1.top();

stack1.pop();

if(temp->val<MinMax[0])

MinMax[0]=temp->val;

else if(temp->val>MinMax[1])

MinMax[1]=temp->val;

if(temp->right)

stack1.push(temp->right);

if(temp->left)

stack1.push(temp->left);

}

return (MinMax[1]-MinMax[0]);

发表于 2015-08-13 15:32:37 回复(0)

灯神萌神

普通树解题思路：遍历二叉树的每个节点，遍历方法有前中后序三种，每次访问一个节点的时候，判断该节点的值和最大，最小值的大小关系，保留最大和最小的结果，直至树遍历结束。

二叉排序树的解题方法：最小值一定是树的最左边的节点（从根节点一直往左）,最大值一定是树的最右边的节点（从根节点一直往右），一直循环直到该节点的下一个节点为空时，找到最大和最小节点。

发表于 2015-08-08 09:30:04 回复(0)

王锦坤

//使用迭代的前序遍历或者中序遍历或者后序遍历,层序遍历，递归遍历
//使用前序遍历
#include<stack>
using namespace std;
struct treenode
{
int value;
treenode *left;
treenode *right;
};
int sort1minmax(treenode *root)
{
treenode *p = root；
int min = p->value;
int max = p->value;
stack st;
while(p)
{
if(p->value > max) { max = p->value;}
if(p->value < min ){ min = p->vlaue;}
if(p->right)
{
st.push_back(p->right);
}
if(p->left)
{
p = p->left;
}
else
{
if(st.IsEmpty())
break;
else
{
p = st.top();
st.pop_up();
if(p->value > max) { max = p->value;}
if(p->value < min ){ min = p->vlaue;}
}
}
return abs(max - min);
}
}

//使用中序遍历
int sort2minmax(treenode *root)
{
treenode *p = root；
int min = p->value;
int max = p->value;
stack st;
while(p || !st.IsEmpty())
{
if(p)
{ p = p->left;
st.push_back(p);
}
else
{
 treenode *temp = st.top();
 st.pop_up();
 if(temp->value > max) { max = p->value;}
 if(temp->value < min ){ min = p->vlaue;}
if(temp->right)
p = temp->right;
}
}
return abs(max-min);
}

//使用后序遍历
int sort3minmax(treenode *root)
{
treenode *p = root；
int min = p->value;
int max = p->value;
stack st;
treenode *r;
while(p || !st.IsEmpty())
{
stack st;
if(p)
{ p = p->left;
st.push_back(p);
}
else
{
 treenode *temp = st.top();
if(temp->right && temp->right != r)
 {
p = temp ->right
 }
else
 {
 tree node *temp = st.top()
 r = temp;
 st.pop_up();
 if(temp->value > max) { max = p->value;}
if(temp->value < min ){ min = p->vlaue;}
 }
}
return abs(max-min);
}

发表于 2015-07-30 19:36:35 回复(1)

大明白

遍历二叉树，找到最大值和最小值，然后输出差值

发表于 2015-03-12 16:44:22 回复(0)

提交观点

问题信息

树

来自：阿里巴巴2015系统工...

上传者：小牧魔法袋

难度：

18条回答 108收藏 7927浏览

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

问题信息

热门推荐

相关试题