2022年微软面试一百道题目精选.docx

第9 题
判断整数序列是不是二元查找树后序遍历成果
题目：输入一种整数数组，判断该数组是不是某二元查找树后序遍历成果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树后序遍历成果：
8
/ \
6 10
/ \ / \
5 7 9 11
因而返回true。
如果输入7、4、6、5，没有哪棵树后序遍历成果是这个序列，因而返回false。
ANSWER:
This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed from mid/post/pre order results. This seems similar. For the problems related to (binary) trees，recursion is the first choice. 
In this problem，we know in post-order results，the last number should be the root. So we have known the root of the BST is 8 in the example. So we can split the array by the root. 
int isPostorderResult(int a[]，int n) {
  return helper(a，0，n-1);
}
int helper(int a[]，int s，int e) {
  if (e==s) return 1;
  int i=e-1;
  while (a[e]>a[i] && i>=s) i--;
  if (!helper(a，i+1，e-1))
    return 0;
  int k = l;
  while (a[e]<a[i] && i>=s) i--;
  return helper(a，s，l);
}
第10 题
翻转句子中单词顺序。
题目：输入一种英文句子，翻转句子中单词顺序，但单词内字符顺序不变。
句子中单词以空格符隔开。为简朴起见，标点符号和普通字母同样解决。
例如输入“I am a student.”，则输出“student. a am I”。
Answer:
Already done this. Skipped.
第11 题
求二叉树中节点最大距离...
如果咱们把二叉树当作一种图，父子节点之间连线当作是双向，
咱们姑且定义"距离"为两节点之间边个数。
写一种程序，
求一棵二叉树中相距最远两个节点之间距离。
ANSWER:
This is interesting... Also recursively，the longest distance between two nodes must be either from root to one leaf，or between two leafs. For the former case，it’s the tree height. For the latter case，it should be the sum of the heights of left and right subtrees of the two leaves’
most least ancestor.
The first case is also the sum the heights of subtrees，just the height + 0.
int maxDistance(Node * root) {
  int depth;
  return helper(root，depth);
}
int helper(Node * root，int &depth) {
  if (root == NULL) {
    depth = 0；return 0;
  }
  int ld，rd;
  int maxleft = helper(root->left，ld);
  int maxright = helper(root->right，rd);
  depth = max(ld，rd)+1;
  return max(maxleft，max(maxright，ld+rd));
}
第12 题
题目：求1+2+…+n，
规定不能使用乘除法、for、while、if、else、swit