本文共 1347 字，大约阅读时间需要 4 分钟。

2021秋招部分笔试题汇总 企业提供原题 00:00:28

空间限制：C/C++ 32M，其他语言64M

给一个二叉查找树（Binary Search Tree）的前序遍历结果数组，打印出所有的叶子节点。

输入描述:

9 8 7 10

输出描述:

解释：因为二叉搜索树的表示为:

9

8 10

7

输出的叶子节点为: 7 10

输入例子1:

输出例子1:

1.首先我们要知道什么是二叉查找树，就是每一个节点的左子树都要小于它，它的右子树都要大于它。

又因为是前序遍历的顺序。我们知道第一个点肯定是根节点，那么我们就找数组里面第一个大于它的元素，第一个大于它的点的右边就是它的右子树，而从它开始到第一个大于它的节点部分就是它的左子树，我们递归的遍历遍历这个过程，当左边界等于右边界时，代表当前元素已经没有孩子了，直接输出这个结点即可。注意一下边界情况即可。`

#include 
   
    #include 
    
     #include 
     
      #include
      
       using namespace std;const int maxn=1e6;int a[maxn];int findindex(int start, int ed ,int target)//找第一个大于它的数 {       int i;    for (i = start; i <= ed; i++) {           if (a[i] > target) return i;    }    return i;}void dfs(int start, int en) {       if (start > en) return;  if (start == en) //没有左右子树  {           cout << a[start] << " ";        return;    }        int index = findindex(start+1, en, a[start]);        if (index <= en) //说明当前结点有左子树和右子树需要分别遍历其左右子树，因为是前序，所以每一个start都是根结点，或者叶子结点        {               dfs(start+1, index-1 );            dfs(index, en );        }        else//说明只有左子树，只需要遍历左子树即可         {               dfs(start+1, index-1);        }}int main() {      char c;   int i=0;   do{     scanf("%d",&a[i++]);     scanf("%c", &c);   }while(c==' ');  // cout<
       <