写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率
这是2015阿里秋招的一个在线笔试题
实现方法很简单，遍历一遍二叉树，，找出最大最小，一相减就可以求出最大的差值
之前在做题的时候居然写递归的方法求值，后面测试了一下，果然结果不对
只要是非递归的的方法遍历都可以很容易找出最大值最小值，效率也比较高，时间复杂度为O（n）。
下面是我用非递归从上往下遍历二叉树的方法
用队列容器即可方便实现。
我写的代码：
#include <iostream> #include <tchar.h>#include <queue> using namespace std; typedef struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }BinaryTreeNode ; int MaxT(BinaryTreeNode *pRoot){int max=pRoot->m_nValue,min=pRoot->m_nValue;if(!pRoot){return 0;}queue<BinaryTreeNode*>qTree;qTree.push(pRoot);while(!qTree.empty()){ BinaryTreeNode *pNode=qTree.front();if(max<pNode->m_nValue){max=pNode->m_nValue;}elseif(min>pNode->m_nValue){min=pNode->m_nValue;}qTree.pop();if(pNode->m_pLeft)qTree.push(pNode->m_pLeft);if(pNode->m_pRight)qTree.push(pNode->m_pRight);}return max-min;}//以先序的方式构建二叉树，输入-1表示结点为空 void CreateBinaryTree(BinaryTreeNode *&pRoot) { int nNodeValue = 0; cin >> nNodeValue; if (-1== nNodeValue) { pRoot = NULL; return; } else { pRoot = new BinaryTreeNode(); pRoot->m_nValue = nNodeValue; CreateBinaryTree(pRoot->m_pLeft); CreateBinaryTree(pRoot->m_pRight); } } void PrintInOrder(BinaryTreeNode *&pRoot) { if (pRoot != NULL) { PrintInOrder(pRoot->m_pLeft); cout << pRoot->m_nValue << " "; PrintInOrder(pRoot->m_pRight); } } int _tmain(int argc, _TCHAR* argv[]) { BinaryTreeNode *pRoot = NULL; CreateBinaryTree(pRoot);cout <<"中序遍历为："<<endl; PrintInOrder(pRoot); cout << endl; int maxabs=MaxT(pRoot);cout<<"最大绝对值为"<<maxabs<<endl; //vector<int> path; //FindPath(pRoot, 22, path); system("pause"); return 0; }
到尽头，也许快乐，或有时孤独，如果心在远方，
