L2-004 这是二叉搜索树吗？

       不得不说AI生成的代码足够简洁和优雅，有很多值得学习的地方。

        本题为我第一次运用二叉树相关的知识做题，解决创建二叉树，后序遍历等问题。在我确定思路和写完大部分代码后，发现自己写的代码继续写下去能写出来，但代码肯定比预计的长，便用豆包试了一下，发现自己的思路没问题，但要写到Ai的地步肯定做不到。

        思路

        首先就是写主函数内容，根据题目条件，我们可以得到：

• 如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则可以确定一颗二叉树。输出“YES”，并输出其后序遍历结果。
• 否则输出“NO”

        主函数伪代码：

int main()
{
    输入 N
    int 数组
    for 0:n
        数组[i]

    判断是否为二叉搜索树前序序列

    判断是否为二叉搜索树镜像前序序列
    
    if(二叉搜索树||二叉搜索树镜像)
    {
        输出 YES
        输出 后序遍历结果
    }
    else
     输出 NO
}

 判断是否为二叉搜索树前序序列

        确定主函数内容后，便是补充各部分内容，首先判断二叉搜索树，根据题意得何为二叉树：

         一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

        这部分单独提出来为一个函数，函数结束之后，我们需要得到：

1. 输入序列是否为二叉搜索树的前序遍历
2. 如果是，得到此二叉树的二叉链表

        这两个任务应该是同时进行的。 那么我们就完全可以假设该序列为二叉搜索树的前序遍历，生成二叉链表，再生成的同时进行判断。根据链表的创建，我们只需得到头节点，便可以得到整个二叉树，所以函数返回头节点更为合适。

        创建二叉链表：

结构体

// 定义节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}//初始化表
};

函数 

// 构建二叉搜索树
TreeNode* buildBST(vector<int> preorder, int index) {
    if (index >= preorder.size()) return NULL;
    TreeNode* node = new TreeNode(val);
    index++;
    node->next=buildBST(preorder,index);
    return node;
}

       这部分只做到了创建一个二叉树，但不是二叉搜索树，并且node->next部分应该是分为左右子树。如果我们考虑只满足：

左子树data<根<右子树data

        但会出现一种情况：

        我们看a图以data为5的根右子树data为9，满足5<9，但5和9都是6的左子树，9>6，不满足条件。 正确应该是b图所示。因此一个结点的左右子树的data应该满足一个区间。

• 左子树data<根<右子树data
• 根<右子树data<根的根

        可能会有疑问，不需要考虑根的根的根嘛？这就体会到递归的好处了，一组满足，组组都会满足了。这样便生成了一个二叉搜索树的二叉链表。

        生成了二叉搜索树：

// 构建二叉搜索树
TreeNode* buildBST(vector<int> preorder, int index, int minVal, int maxVal) {
    printf("index=%d\n",index);
    if (index >= preorder.size()) return NULL;
    int val = preorder[index];
    if (val < minVal || val >= maxVal) return NULL;
    TreeNode* node = new TreeNode(val);
    index++;
    node->left = buildBST(preorder, index, minVal, val);
    node->right = buildBST(preorder, index, val, maxVal);
    return node;
}

        这里可以确定两个必须得参数是数组preorder和数组下标index ，我们不能通过返回值head得到输入序列是否为二叉搜索树的前序遍历，但是可以确定如果输入序列为二叉搜索树的前序遍历，那么一定能生成二叉树。当生成二叉树时，一定会满足index >= preorder.size()， 所以我们可以通过判断函数结束后，index的值来确定是否为二叉搜索树的前序遍历。这里注意要将传参的index改为引用，达到静态变量的效果。

TreeNode* buildBST(vector<int> preorder, int& index)

判断是否为二叉搜索树镜像前序序列

        与二叉搜索树相比，镜像只是变为：  

• 其左子树中所有结点的键值大于该结点的键值；
• 其右子树中所有结点的键值小于等于该结点的键值；

所以我们只需更换一个地方，交换左右子树递归参数：

    node->left = buildBST(preorder, index, minVal, val);

    node->right = buildBST(preorder, index, val, maxVal);

变为： 

    node->left = buildMirrorBST(preorder, index, val, maxVal);

    node->right = buildMirrorBST(preorder, index, minVal, val);

 

完整函数 ：

// 构建镜像二叉搜索树
TreeNode* buildMirrorBST(vector<int> preorder, int& index, int minVal, int maxVal) {
    if (index >= preorder.size()) return NULL;
    int val = preorder[index];
    if (val < minVal || val >= maxVal) return NULL;
    TreeNode* node = new TreeNode(val);
    index++;
    node->left = buildMirrorBST(preorder, index, val, maxVal);
    node->right = buildMirrorBST(preorder, index, minVal, val);
    return node;
}

然后便是补全主函数，这里不再介绍，直接上完整代码：

#include <iostream>
#include <vector>
using namespace std;

// 定义节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}//初始化表
};

// 构建二叉搜索树
TreeNode* buildBST(vector<int> preorder, int& index, int minVal, int maxVal) {
    printf("index=%d\n",index);
    if (index >= preorder.size()) return NULL;
    int val = preorder[index];
    if (val < minVal || val >= maxVal) return NULL;
    TreeNode* node = new TreeNode(val);
    index++;
    node->left = buildBST(preorder, index, minVal, val);
    node->right = buildBST(preorder, index, val, maxVal);
    return node;
}

// 构建镜像二叉搜索树
TreeNode* buildMirrorBST(vector<int> preorder, int& index, int minVal, int maxVal) {
    if (index >= preorder.size()) return NULL;
    int val = preorder[index];
    if (val < minVal || val >= maxVal) return NULL;
    TreeNode* node = new TreeNode(val);
    index++;
    node->left = buildMirrorBST(preorder, index, val, maxVal);
    node->right = buildMirrorBST(preorder, index, minVal, val);
    return node;
}

// 后序遍历
void postorderTraversal(TreeNode* root, vector<int>& postorder) {
    if (root == NULL) return;
    postorderTraversal(root->left, postorder);
    postorderTraversal(root->right, postorder);
    postorder.push_back(root->val);
}

// 释放树的内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    int n;
    cin >> n;
    vector<int> preorder(n);
    for (int i = 0; i < n; i++) {
        cin >> preorder[i];
    }

    int index = 0;
    TreeNode* root = buildBST(preorder, index, -0x3f3f3f, 0x3f3f3f);
    if (index == preorder.size()) {
        vector<int> postorder;
        postorderTraversal(root, postorder);
        cout << "YES" << endl;
        for (int i = 0; i < postorder.size(); i++) {
            if (i != 0) cout << " ";
            cout << postorder[i];
        }
        freeTree(root);
        return 0;
    }

    index = 0;
    root = buildMirrorBST(preorder, index, -0x3f3f3f, 0x3f3f3f);
    if (index == preorder.size()) {
        vector<int> postorder;
        postorderTraversal(root, postorder);
        cout << "YES" << endl;
        for (int i = 0; i < postorder.size(); i++) {
            if (i != 0) cout << " ";
            cout << postorder[i];
        }
        freeTree(root);
        return 0;
    }
    // cout<<index<<endl;
    cout << "NO" << endl;
    return 0;
}

声明

        本代码为AI所写修改而来，初版并没有通过测试点，我做了简单修改才通过，所以AI目前并不能完全的理解题目，但已经很强了。