2025年微软面试一百道题目

第 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]=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...