首页 / 算法 / 2015阿里秋招其中一个算法题(经典)
2015阿里秋招其中一个算法题(经典)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2015阿里秋招其中一个算法题(经典),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1820字,纯文字阅读大概需要3分钟。
内容图文
写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率
这是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;
}
else
if(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;
}
原文:http://blog.csdn.net/u014082714/article/details/44276001
内容总结
以上是互联网集市为您收集整理的2015阿里秋招其中一个算法题(经典)全部内容,希望文章能够帮你解决2015阿里秋招其中一个算法题(经典)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。