C++实现LeetCode(98.验证二叉搜索树)

 更新时间:2021年7月20日 10:00  
这篇文章主要介绍了C++实现LeetCode(98.验证二叉搜索树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
2
/ \
1   3
Output: true

Example 2:

    5
/ \
1   4
/ \
3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.

这道验证二叉搜索树有很多种解法,可以利用它本身的性质来做,即左<根<右,也可以通过利用中序遍历结果为有序数列来做,下面我们先来看最简单的一种,就是利用其本身性质来做,初始化时带入系统最大值和最小值,在递归过程中换成它们自己的节点值,用long代替int就是为了包括int的边界条件,代码如下:

C++ 解法一:

// Recursion without inorder traversal
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode* root, long mn, long mx) {
        if (!root) return true;
        if (root->val <= mn || root->val >= mx) return false;
        return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
    }
};

Java 解法一:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean valid(TreeNode root, long low, long high) {
        if (root == null) return true;
        if (root.val <= low || root.val >= high) return false;
        return valid(root.left, low, root.val) && valid(root.right, root.val, high);
    }
}

这题实际上简化了难度,因为有的时候题目中的二叉搜索树会定义为左<=根<右,而这道题设定为一般情况左<根<右,那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话,那么下边两个数用中序遍历无法区分:

   20       20
/           \
20           20

它们的中序遍历结果都一样,但是左边的是 BST,右边的不是 BST。去掉等号的条件则相当于去掉了这种限制条件。下面来看使用中序遍历来做,这种方法思路很直接,通过中序遍历将所有的节点值存到一个数组里,然后再来判断这个数组是不是有序的,代码如下:

C++ 解法二:

// Recursion
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> vals;
        inorder(root, vals);
        for (int i = 0; i < vals.size() - 1; ++i) {
            if (vals[i] >= vals[i + 1]) return false;
        }
        return true;
    }
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
};

Java 解法二:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    public void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

下面这种解法跟上面那个很类似,都是用递归的中序遍历,但不同之处是不将遍历结果存入一个数组遍历完成再比较,而是每当遍历到一个新节点时和其上一个节点比较,如果不大于上一个节点那么则返回 false,全部遍历完成后返回 true。代码如下:

C++ 解法三:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return inorder(root, pre);
    }
    bool inorder(TreeNode* node, TreeNode*& pre) {
        if (!node) return true;
        bool res = inorder(node->left, pre);
        if (!res) return false;
        if (pre) {
            if (node->val <= pre->val) return false;
        }
        pre = node;
        return inorder(node->right, pre);
    }
};

当然这道题也可以用非递归来做,需要用到栈,因为中序遍历可以非递归来实现,所以只要在其上面稍加改动便可,代码如下:

C++ 解法四:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode *p = root, *pre = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre && p->val <= pre->val) return false;
            pre = p;
            p = p->right;
        }
        return true;
    }
};

Java 解法四:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root, pre = null;
        while (p != null || !s.empty()) {
            while (p != null) {
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            if (pre != null && p.val <= pre.val) return false;
            pre = p;
            p = p.right;
        }
        return true;
    }
}

最后还有一种方法,由于中序遍历还有非递归且无栈的实现方法,称之为 Morris 遍历,可以参考博主之前的博客 Binary Tree Inorder Traversal,这种实现方法虽然写起来比递归版本要复杂的多,但是好处在于是 O(1) 空间复杂度,参见代码如下:

C++ 解法五:

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root) return true;
        TreeNode *cur = root, *pre, *parent = NULL;
        bool res = true;
        while (cur) {
            if (!cur->left) {
                if (parent && parent->val >= cur->val) res = false;
                parent = cur;
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    if (parent->val >= cur->val) res = false;
                    parent = cur;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(98.验证二叉搜索树)的文章就介绍到这了,更多相关C++实现验证二叉搜索树内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

相关文章

  • 深入学习C++智能指针之shared_ptr与右值引用的方法

    智能指针的核心实现技术是引用计数,每使用它一次,内部引用计数加1,每析构一次内部的引用计数减1,减为0时,删除所指向的堆内存,今天通过本文给大家分享C++智能指针之shared_ptr与右值引用的方法,需要的朋友跟随小编一起看看吧...2021-07-13
  • 浅谈c++性能测试工具google benchmark

    本文将会介绍如何使用模板以及参数生成器来批量生成测试用例,简化繁琐的性能测试代码...2021-06-26
  • 详解C++实现匈牙利算法

    匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法,是因为算法很大一部分是基于以前匈牙利数学家Dénes K&#337;nig和Jen&#337; Egerváry的工作之上创建起来的...2021-06-17
  • C++实现LeetCode(37.求解数独)

    这篇文章主要介绍了C++实现LeetCode(37.求解数独),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • C++中NULL与nullptr的区别对比

    nullptr是c++11中的关键字,下面这篇文章主要介绍了C++中NULL与nullptr区别的相关资料,对大家来说还是挺实用的,需要的朋友可以参考下...2021-05-16
  • 一文搞懂C++中的四种强制类型转换

    很多朋友向小编了解C语言中怎么进行强制类型转换呢?在这小编告诉大家强制类型转换可以分为两种,一种是隐式类型转换一种是显示类型转换,下面通过示例代码给大家介绍下,需要的朋友参考下吧...2021-07-07
  • C++实现聊天小程序

    这篇文章主要为大家详细介绍了C++实现聊天小程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-07-01
  • C++/CLI在vs上的安装和初步使用教程

    本文给大家介绍C++/CLI在vs上的安装和初步使用,本文通过图文并茂的形式给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧...2021-07-02
  • 深入浅析C++ traits技术

    traits就是提取“被传进的对象”对应的返回类型,让同一个接口实现对应的功能。因为STL的算法和容器是分离的,两者通过迭代器链接,本文通过实例代码给大家介绍C++ traits技术,感兴趣的朋友一起看看吧...2021-05-30
  • C++解析特殊符号tab、换行符号实例代码

    这篇文章主要给大家介绍了关于C++解析特殊符号tab、换行符号的相关资料,这个功能在我们日常开发中经常会遇到,需要的朋友可以参考下...2021-05-16
  • 详解C++的反调试技术与绕过手法

    反调试技术,恶意代码会用它识别自身是否被调试,或者让调试器失效,给反病毒工程师们制造麻烦,拉长提取特征码的时间线,本章将具体总结常见的反调试基础的实现原理以及如何过掉这些反调试手段,从而让我们能够继续分析恶意代码...2021-06-24
  • 线段树详解以及C++实现代码

    线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中,这篇文章主要给大家介绍了关于线段树以及C++实现的相关资料,需要的朋友可以参考下...2021-07-19
  • c++多线程为何要使用条件变量详解

    多线程是多任务处理的一种特殊形式,下面这篇文章主要给大家介绍了关于c++多线程为何要使用条件变量的相关资料,需要的朋友可以参考下...2021-06-04
  • C++实现LeetCode(51.N皇后问题)

    这篇文章主要介绍了C++实现LeetCode(51.N皇后问题),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • 在Visual Studio Code中配置C++编译环境的问题

    关于Visual Studio Code对C++环境的配置方法应该有好多种,我这里用到了其中的两种,具体内容详情文中给大家详细介绍,对Visual Studio Code配置C++编译环境相关知识感兴趣的朋友一起看看吧...2021-07-05
  • 从c++标准库指针萃取器谈一下traits技法(推荐)

    本篇文章基于gcc中标准库源码剖析一下标准库中的模板类pointer_traits,并且以此为例理解一下traits技法,对c++ traits技法源码分析感兴趣的朋友跟随小编一起看看吧...2021-07-14
  • C++实现二分法求方程近似解

    这篇文章主要为大家详细介绍了C++实现二分法求方程近似解,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-05-09
  • C++ 实现桶排序的示例代码

    桶排序或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子,本文详细的介绍了如何实现,感兴趣的可以了解一下...2021-07-12
  • C++基于灰度图上色GrayToColorFromOther的实现

    本文主要介绍了C++基于灰度图上色GrayToColorFromOther的实现,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧...2021-07-19
  • VS2019实现C++的第一个MFC程序

    本文主要介绍了VS2019实现C++的第一个MFC程序,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-06-07