首页 > 试题广场 >

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

[问答题]
写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这颗二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。
推荐
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&gt;=b&amp;&amp;a&gt;=c) return a; if(b&gt;=a&amp;&amp;b&gt;=c) return b; return c; } public int getMin(int a,int b,int c) { if(a&lt;=b&amp;&amp;a&lt;=c) return a; if(b&lt;=a&amp;&amp;b&lt;=c) return b; return c; }</pre> <br />
发表于 2015-08-21 15:33:37 回复(0)
<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&lt;head.val){ if(head.leftChird == null){ head.leftChird == new btreeNode(val); }else{ addNode(head.leftChird ,val); }else if(val&gt;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 &gt; 0){ btreeNode head = new btreeNode(arrs(0)); for(int i=0;i&lt;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> <br />
发表于 2015-08-21 10:42:38 回复(0)
解题思路:
将问题转化为求无序数组中的最大值和最小值,只需在遍历二叉树的过程中分别记住最大值和最小值即可。遍历算法建议用中序遍历的非递归算法,可在O(n)内解决。
编辑于 2015-08-20 21:29:07 回复(0)
<div> 算法思想:<br /> &nbsp;&nbsp;&nbsp; 1、初始化一个栈,<br /> &nbsp;&nbsp;&nbsp; 2、将二叉树的元素依次压入到栈中,初始化最大值max和最小值min为根元素<br /> &nbsp;&nbsp;&nbsp; 3、出栈的元素依次与max和min比较<br /> &nbsp;&nbsp;&nbsp; 4、result=max-min<br /> </div>
发表于 2015-08-20 21:21:34 回复(0)
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&lt;int&gt; list = new ArrayList&lt;int&gt;(); Stack&lt;TreeNode&gt; mStack = new Stack&lt;TreeNode&gt;(); 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]&gt;a[1]){ int min = a[1]; int max = a[0]; }else{ int min = a[0]; int max = a[1]; } for(int i = 2; i&lt;list.size(); i++){ if(min &gt; a[i]){ min = a[i]; }else if(max &lt; a[i]){ max = a[i]; } } return max -min; }</pre> <br />
发表于 2015-08-18 09:24:01 回复(0)
<div> 遍历二叉树,找出最大和最小值。如果二叉树采用数组实现,则JAVA代码如下,其时间复杂度为O(n),空间复杂度为O(1)。<br /> public class BinaryTree {<br /> &nbsp;&nbsp;&nbsp; public static void main(String[] args) {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int[] tree = {1,2,3,-1,5,7,-1,10,19};//用数组实现二叉树,其中-1表示该位置没有节点<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; System.out.println("最大差值是:" + getMaxGap(tree));<br /> &nbsp;&nbsp;&nbsp; }<br /> &nbsp;&nbsp;&nbsp; public static int getMaxGap(int[] tree) {<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; int result = 0;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int maxindex = 0;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int minindex = 0;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(tree != null &amp;&amp; tree.length &gt; 1) {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for(int i = 1; i &lt; tree.length; i++) {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(tree[i] &gt; tree[maxindex]) maxindex = i;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(tree[i] &lt; tree[minindex]) minindex = i;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result = tree[maxindex] - tree[minindex];<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return result;<br /> &nbsp;&nbsp;&nbsp;&nbsp;}<br /> }<br /> </div>
发表于 2015-08-17 10:56:09 回复(0)
<pre class="prettyprint lang-cpp">#define MAX_TREE_SIZE 100 typedef struct BiTNode { int m_nValue; struct BiTNode* m_pLChild; &nbsp; struct BiTNode* m_pRChild; } BiTNode; bool g_InvalidInput = false; int MaxDiffOfNodes(BiTNode* pRoot) { &nbsp; int ret = 0; &nbsp; 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-&gt;m_nValue &gt; max ) { max = pNode-&gt;m_nValue; } if( pNode-&gt;m_nValue &lt; min ) { min = pNode-&gt;m_nValue; } if( NULL != pNode-&gt;m_pLChild ) { queue[rear++] = pNode-&gt;m_pLChild; } if( NULL != pNode-&gt;m_pRChild ) { queue[rear++] = pNode-&gt;m_RLChild; } } ret = max - min; g_InvalidInput = false; } return ret; }</pre> <br />
发表于 2015-08-16 12:53:47 回复(0)
<pre class="prettyprint lang-java"> </pre> public class FindTreeMax {<br /> &nbsp;&nbsp;&nbsp; <br /> &nbsp;&nbsp;&nbsp; static int max = -99999999;<br /> &nbsp;&nbsp;&nbsp; static int min = 999999999;<br /> &nbsp;&nbsp;&nbsp; <br /> &nbsp;&nbsp;&nbsp; public static void getMax(Node head){<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if(head!=null){<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; max = head.value &gt; max ? head.value : max;<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; min = head.value &lt; min ? head.value : min;<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; getMax(head.left);<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; getMax(head.right);<br /> &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br /> &nbsp;&nbsp;&nbsp; }<br /> }<br /> <br /> class Node {<br /> &nbsp;&nbsp;&nbsp; public int value;<br /> &nbsp;&nbsp;&nbsp; public Node left;<br /> &nbsp;&nbsp;&nbsp; public Node right;<br /> &nbsp;&nbsp;&nbsp; public Node(int data) {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this.value = data;<br /> &nbsp;&nbsp;&nbsp; }<br /> }<br />
发表于 2015-08-15 22:16:48 回复(0)
&lt;pre class="prettyprint lang-java"&gt;public static long getMaxAbs(TreeNode root){ getMaxAbsHelper(root,Integer.MIN_VALUE,Integer.MAX_VALUE); }&lt;/pre&gt; &lt;pre class="prettyprint lang-java"&gt; public static long getMaxAbsHelper(TreeNode root,int max,int min){ if(root == null){ return 0; } if(root.val&amp;gt;max){ max = root.val; } if(root.val &amp;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); }&lt;/pre&gt; &lt;br /&gt;
发表于 2015-08-14 20:59:53 回复(0)
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)