Tomcat LVS 软件开发 windows elasticsearch redis常用语句 pip UIkit flowjs bootstrap管理系统模板 jquery去掉空格 jq延时 linux查看mysql进程 mysql倒序 bootstrap文件上传样式 coreldraw入门学习 mysql或者条件 python输入输出 python文件写入 python图形界面开发 python正则表达式语法 python的lambda函数 java运行环境配置 java遍历list集合 dll文件下载 通达信金融终端官网 din字体下载 图片生成网址 html特殊符号 2k14生涯模式修改器 通讯录管理系统 mac地址修改 批处理if 微信小程序开发实例 foobar2000插件 红米3和红米3s的区别 max2014 jdk8安装教程 方正倩体 adb工具包
当前位置: 首页 > 学习教程  > 编程语言

26 验证二叉搜索树(leecode 98)

2021/2/13 18:29:03 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

1 问题 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树2 解法 中序遍历下&#xff0…

1 问题

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

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

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

在这里插入图片描述

2 解法

中序遍历下,输出的二叉搜索树节点的数值是有序序列。
有了这个特性,「验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。」

2.1 递归法

2.1.1 使用额外数组
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    void traversal(TreeNode* root)
    {
        if(root == nullptr)
            return;
        traversal(root->left); //左
        res.push_back(root->val); //根
        traversal(root->right); //右
    }
    bool isValidBST(TreeNode* root) {
        //初始化,删除数组中全部元素
        res.clear(); 
        //获得中序遍历的结果数组
        traversal(root);
        //判断数组是否递增
        for(int i = 1; i < res.size(); i++)
        {
            //注意=,二叉搜索树中不可有相等元素
            if(res[i - 1] >= res[i])
                return false;
        }
        return true;
    }
};
2.1.2 不使用数组
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //记录前一个节点
    TreeNode* pre = nullptr; 
    bool isValidBST(TreeNode* root) {
        //空节点也是二叉搜索树
        if(root == nullptr)
            return true;
        //中序遍历
        bool left = isValidBST(root->left); //左
        if(pre != nullptr && pre->val >= root->val)    //中
            return false;
        pre = root;
        bool right = isValidBST(root->right); //右
        return left && right;
    }
};

2.2 迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        //保存上一个节点
        TreeNode* pre = nullptr;
        //指向当前遍历的节点
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty())
        {
            //左节点不为空,则遍历左子树
            if(cur != nullptr)                                 //左
            {
                st.push(cur);
                cur = cur->left;
            }                               
            else
            {
                cur = st.top();                   //中
                st.pop();                                   
                if(pre != nullptr && cur->val <= pre->val)          
                    return false;   
                //保存当前结点
                pre = cur;
                cur = cur->right;                            //右
            }
        } 
        return true;
    }
};

本文链接: http://www.dtmao.cc/news_show_700253.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?