L2-004 这是二叉搜索树吗？-团体程序设计天梯赛GPLT

以你之姓@ 2023-07-06 11:58 14阅读 0赞

> 题目来源：团体程序设计天梯赛-练习集  
> 题目地址：[L2-004 这是二叉搜索树吗？][L2-004]

![problem][]

### 题目大意 ###

给定一个长度为  n n n 的序列，判断这是否是对一棵**二叉搜索树**或**其镜像**进行前序遍历的结果。如果是，则在一行中输出 YES ，然后在下一行输出该树后序遍历的结果，否者直接输出 NO。

### 题目分析 ###

**1. 预备知识**  
前序遍历：先访问根节点，再遍历左子树，最后遍历右子树。

后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。  
（注意：遍历子树的时候也要按照相应的的方式遍历。）

二叉搜索树的基本性质（如题目描述所示）

**2. 结题要义**  
首先，我们假设输入的序列  a \[   \] a\[\\ \] a\[ \] 就是一棵二叉搜索树进行前序遍历的结果， l l l 和  r r r 分别为序列  a \[   \] a\[\\ \] a\[ \] 的左右边界。

根据前序遍历的性质，我们可以知道  a \[ l \] a\[l\] a\[l\] 即为这棵树的根节点、  l + 1 l+1 l\+1 为左子树的左边界，  r r r 为右子树的右边界。然后我们定义两个指针  t l tl tl 、 t r tr tr 分别表示右子树的左边界、左子树的右边界。（**注意哪个对应哪个**）

初始化  t l = l + 1 tl = l+1 tl=l\+1 、 t r = r tr=r tr=r，接着根据二叉树搜索树的性质 ， t l tl tl 往右移动，找到第一个大于或等于根节点  a \[ l \] a\[l\] a\[l\] 的节点、 t r tr tr往右移动，找到第一个小于根节点  a \[ l \] a\[l\] a\[l\] 的节点。过程如下图所示，  
![1][]  
这样就确定了序列中根节点、左子树和右子树的位置，我们**递归进行这个这个过程**，就可以得到整棵树的结构，过程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]  
为了简便，我们可以省去建树的过程，**在确定了序列中根节点、左子树和右子树的位置后，就直接进行后序遍历**。由确定子树范围的过程可得，若这是一颗二叉搜索树，则必有  t l − t r = 1 tl-tr=1 tl−tr=1 ，要是不满足这个条件，我们就直接停止遍历。

访问根节点时，我们可以将根节点放入  v e c t o r vector vector 中（ v e c t o r vector vector即为后序遍历序列）。最后我们**通过判断  v e c t o r vector vector 中的元素个数是否等于  n n n 来判断这是否为二叉搜索树**。

如果等于  n n n ，就可以输出  v e c t o r vector vector ；否则就判断是否为镜像。至于求判断镜像的过程也基本和上诉无异，区别在于确定子树范围的条件而已。

### 代码如下 ###

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e3 + 10;
    int n, flag;
    /** * a[]用于存储输入的前序遍历序列 * ans用于存储后序遍历的结果 */
    int a[maxn];
    vector<int> ans;
    
    /** * 后序遍历这颗二叉树 * */
    void dfs(int l, int r) { 
        if (l > r) return ;
        //tl表示右子树的左边界，tr表示左子树的右边界
        int tl = l + 1, tr = r;
        if (flag) { 
            //判断二叉搜索树的“镜像”
            while (tl <= r && a[tl] >= a[l]) tl++;
            while (tr > l && a[tr] < a[l]) tr--;
        } else { 
            //判断二叉搜索树
            while (tl <= r && a[tl] < a[l]) tl++;
            while (tr > l && a[tr] >= a[l]) tr--;
        }
        //不满足二叉搜索树的条件
        if (tl - tr != 1) return ;
        //访问左子树
        dfs(l + 1, tr);
        //访问右子树
        dfs(tl, r);
        //访问根节点
        ans.push_back(a[l]);
    }
    
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        //先检查是不是二叉搜索树的“镜像”
        dfs(1, n);
        //如果不满足，则再检查是不是二叉搜索树
        if (ans.size() != n) { 
            flag = 1;
            ans.clear();
            dfs(1, n);
        }
        if (ans.size() != n) { 
            cout << "NO" << endl;
        } else { 
            cout << "YES" << endl;
            for (int i = 0; i < n; i++) { 
                cout << ans[i] << (i == n -1 ? '\n' : ' ');
            }
        }
        return 0;
    }

--------------------

如果本文对你有所帮助，记得点个赞哦~

[L2-004]: https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192
[problem]: https://img-blog.csdnimg.cn/20200218202649324.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200222113859440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222114633545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70