【LeetCode】 T98. 验证二叉搜索树 递归过程有点难理解

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

// 二叉排序树中序遍历有序
long last = LONG_MIN; // 父节值
bool flag = true; // 父结点是否大于子节点
bool IsBSTree(TreeNode* root){
    if(!root)
        return true;
    
    // 遍历左子树
    if(flag && root->left)
        IsBSTree(root->left);
    
    // 做判断
    // 当前节点小于等于上一个节点,不是二叉排序树
    if(root->val <= last)
        flag = false;
    last = root->data; // 记录父节点值
    
    //遍历右子树
    if(root->rchild && flag != 0)
        IsBSTree(root->right);
    
    // 树都遍历完 或 不是二叉排序树,就退出
    return flag;
}

本文链接:https://ariser.cn/index.php/archives/366/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!