合法二叉搜索树——中序遍历判断结果是否为递增数组

悠悠 2023-02-11 04:48 3阅读 0赞

实现一个函数，检查一棵二叉树是否为二叉搜索树。  
示例 1:

输入:  
2  
/  
1 3  
输出: true

示例 2:

输入:  
5  
/  
1 4  
/  
3 6  
输出: false  
解释: 输入为: \[5,1,4,null,null,3,6\]。  
根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/legal-binary-search-tree-lcci

一开始想了好久不知道用啥方法（大二的数据结构白学了），后来看别人的题解，原来合法二叉搜索树的中序遍历序列为一个递增的序列。二叉搜索树（二叉排序树、二叉查找树）：它或者是一颗空树，或者具有下列性质：若它的左子树不为空，则左子树上的所有结点的值都小于它的值；若它的右子树不空，则右子树上的所有结点值都大于它的值。它的左右子树也为二叉搜索树。

下面是代码，简单的中序遍历把元素装进vector数组里面，然后循环一波判断数组是否递增即可。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    # include<iostream>
    # include<vector>
    using namespace std;
    class Solution { 
    public:
        void Mid(TreeNode * root,vector<int> &tot)
        { 
            if(root==NULL) return;
            Mid(root->left,tot);
            tot.emplace_back(root->val);
            Mid(root->right,tot);
        }
        bool isValidBST(TreeNode* root) { 
            if(root==NULL) return true;
             vector<int> tot;
             bool judge=true;
             Mid(root,tot);
             for(int i=0;i<tot.size()-1;i++)
             { 
                 if(tot[i+1]>tot[i]) continue;
                 else{ judge=false; break;}
             }
             return judge;
        }
    };