}
}
int find(BinaryTreeNode *pRoot) { static int min = MIN;//定义一个足够大的数 static int max = MAX;//定义一个足够小的数 if(min>pRoot->val) min = pRoot->val; if(max<pRoot->val) max = pRoot->val; if(pRoot->lChild!=NULL) find(pRoot->lChild); if(pRoot->rChild!=NULL) find(pRoot->rChild); return max-min; }
/** *1)先构造二叉树; *2)利用二叉树遍历的方法得到min和max即可; */ class Test{ public static void main(String[] args) { TestALBB mTestALBB=new TestALBB(); int array[]={1,5,-5,9,-10}; mTestALBB.createTree(array); int value=mTestALBB.getMax(); System.out.println("value: "+value); } } class TestALBB{ public int min=0; public int max=0; public TreeNode t=null; /* * 有一组数据 构造二叉树; */ public void createTree(int array[]){ //方法1--》顺序存储构造二叉排序树;利用队列; TreeNode t=new TreeNode(); t.data=array[0]; t.left=t.right=null; int i=1; java.util.Queue<TreeNode> mQueue=new java.util.LinkedList<TreeNode>(); mQueue.offer(t); TreeNode temp=null; while(i<array.length-1){ temp=mQueue.poll(); TreeNode left=new TreeNode(); left.data=array[i]; left.left=left.right=null; temp.left=left; mQueue.offer(left); TreeNode right=new TreeNode(); right.data=array[i+1]; right.left=right.right=null; temp.right=right; mQueue.offer(right); i=i+2; } this.t=t; } /* * 利用先序排序得到 min和 max */ public void getValue(TreeNode t){ if(t!=null){ if(t.data>max)max=t.data; else if(t.data<min)min=t.data; } if(t.left!=null){ getValue(t.left); } if(t.right!=null){ getValue(t.right); } } public int getMax(){ this.getValue(this.t); return Math.abs(max-min); } } /** * * @author Administrator * 节点的数据结构 * */ class TreeNode{ public TreeNode right=null; public TreeNode left=null; public int data=0; }
struct TreeNode { int val; TreeNode *left; TreeNode *right; }; int solve(TreeNode *root) { if (root == NULL) return -1; int ma = 0, mi = 0; queue<TreeNode *> que; TreeNode *p = root; que.push(p); ma = max(ma, p->val); mi = min(mi, p->val); while (!que.empty()) { TreeNode *q = que.top(); que.pop(); if (q->left) { que.push(q->left); ma = max(ma, q->left->val); mi = min(mi, q->left->val); } if (q->right) { que.push(q->right); ma = max(ma, q->right->val); mi = min(mi, q->right->val); } } return ma - mi; }
public class BiTree { private Node root; private static int max; private static int min; /** * 创建内部节点类 **/ private class Node { // 左节点 private Node leftChild; // 右节点 private Node rightChild; // 节点对应的值 private int data; public Node(int data) { leftChild = null; rightChild = null; this.data = data; } }// class Node public BiTree() { root = null; } /* * 递归的创建二叉树 */ public void buildTree(Node node, int data) { if (root == null) {// 如果根节点为空,创建根节点 root = new Node(data); } else { if (data < node.data) {// 插入到左子树 if (node.leftChild == null) {// 左节点为空,直接创建值为data的左节点 node.leftChild = new Node(data); } else {// 左节点不为空,调用buildTree函数插到左子树中 buildTree(node.leftChild, data); } } else { if (node.rightChild == null) { node.rightChild = new Node(data); } else { buildTree(node.rightChild, data); } } } }// end buildTree public int getMax(Node node) { if (node != null) { max = Math.max(max, node.data); getMax(node.rightChild); } return max; } public int getMin(Node node) { if (node != null) { min = Math.min(min, node.data); getMin(node.rightChild); } return min; } public static void main(String ars[]) { int[] a = { 6, 4, 8, 3, 5, 7, 9 }; BiTree binTree = new BiTree(); for (int i = 0; i < a.length; i++) { binTree.buildTree(binTree.root, a[i]); } min = binTree.root.data; // System.out.println("前序遍历"); max = binTree.getMax(binTree.root); min = binTree.getMin(binTree.root); System.out.println(max - min); } }
//遍历的同时维护最大值,最小值//时间复杂度 o(n)public class MaxDifference { private int result = Integer.MIN_VALUE; private int max = Integer.MIN_VALUE; private int min = Integer.MAX_VALUE; public int maxDifference(TreeNode root){ if (root == null) { System.out.print("error"); return -1; } return preOrder(root); } public int preOrder(TreeNode root){ if(root.val > max) max = root.val; if(root.val < min) min = root.val; if (result < Math.abs(max - min)) { result = Math.abs(max - min); } if (root.left != null) { preOrder(root.left); } if (root.right != null){ preOrder(root.right); } return result; } }
int min,max;int find(TreeNode * root)
{
min = root->value;
max = root->value;
findRecursive(root);
return max - min;
}
findRecursive(TreeNode * root)
{
if(root->left != NULL)
{
if(root->left->value<min)
{
min = root->left->value;
}
if(root->left->value>max){ max = root->left->value; } findRecursive(root->left);}
if(root->right != NULL){ if(root->right->value<min) { min = root->right->value; } if(root->right->value>max)}{ max = root->right->value; } findRecursive(root->right);}