名企招聘经典口试编程题集锦[第1-10题]

名企招聘经典面试编程题集锦[第1-10题]

声明：所有试题均来自网络。解答仅作参考，如对解答有疑问，或者有更好的解法，欢迎留言交流。

1、二叉树的深度

输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）

形成树的一条路径，最长路径包含结点的个数为树的深度。

struct BinaryTreeNode{int value;BinaryTreeNode* left;BinaryTreeNode* right;};int DepthOfTree(BinaryTreeNode* root){if (root == NULL)return 0;elsereturn 1 + max(DepthOfTree(root->left),DepthOfTree(root->right));}

2、二叉树中结点的最大距离

我们姑且定义"距离"为两结点之间边的个数。
写一个函数，求一棵二叉树中相距最远的两个结点之间的距离。

template<typename T>class myStack{public:void push(const T&);void pop();const T& min()const;private:stack<T> data;stack<T> minData;};template<typename T> void myStack<T>::push(const T& value){data.push(value);if(minData.size()==0 || value<minData.top())minData.push(value);elseminData.push(minData.top());}template<typename T> void myStack<T>::pop(){assert(data.size()>0 && minData.size()>0);data.pop();minData.pop();}template<typename T> const T& myStack<T>::min()const{assert(data.size()>0 && minData.size()>0);return minData.top();}

5、求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

int FindGreatestSumOfSubArray(int* data,int length){if(data==NULL || length<1)throw exception("invalid parameters!");int sum=0;int max = 0x80000000;for(int i=0;i!=length;++i){sum+=*(data+i);if(sum<0)sum=0;else if(sum>max)max = sum;}return max;}

6、在二元树中找出和为某一值的所有路径

输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10  
  / \   
 5   12   
/ \   
4  7
则打印出两条路径：10, 12和10, 5, 7。

9、判断一个整数序列是不是二元查找树的后序遍历结果
输入一个整数数组，判断该数组是不是某二叉查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
10、翻转句子中单词的顺序。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
//翻转字符串void Reverse(char* first,char* last){if(first==NULL || last==NULL)return;while (first<last){char temp = *first;*first++ = *last;*last-- = temp;}}void ReverseSentence(char* str){if(str == NULL)return;char* first = str;char* last =str;while(*last!='\0')++last;--last;Reverse(first,last);last=first;while(true){while(*last!=' ' && *last!='\0')++last;--last;Reverse(first,last);if(*(last+1)==' '){last+=2;first=last;}elsebreak;}}