专栏首页Michael阿明学习之路程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

1. 题目

实现一个函数,检查一棵二叉树是否为二叉搜索树。

示例 1:
输入:
    2
   / \
  1   3
输出: true

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

2. 解题

  • 该题要求严格,不允许相等
  • 中序遍历即可
class Solution {
public:
    bool isValidBST(TreeNode* root) {
    	stack<TreeNode*> stk;
    	TreeNode* tp, *prev = NULL;
    	while(root || !stk.empty())
    	{
    		while(root)
    		{
    			stk.push(root);
    			root = root->left;
    		}
    		tp = stk.top();
    		stk.pop();
    		if(prev != NULL && prev->val >= tp->val)
    			return false;
    		prev = tp;
    		root = tp->right;
    	}
    	return true;
    }
};
  • 递归
  • 返回子树的最小值和最大值,供上一层判断
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        bool ans = true;
        check(root,ans);
        return ans;
    }

    vector<int> check(TreeNode* root, bool& ans)
    {
        if(!root || ans == false)
        	return {};
        vector<int> l, r;
        l = check(root->left, ans);
        r = check(root->right, ans);
        if(l.empty() && r.empty())
        	return {root->val, root->val};
        else if(!l.empty() && r.empty())
        {
        	if(l[1] >= root->val)
        		ans = false;
        	return {l[0], root->val};
        }
        else if(l.empty() && !r.empty())
        {
        	if(r[0] <= root->val)
        		ans = false;
        	return {root->val, r[1]};
        }
        else
        {
        	if(l[1] >= root->val || r[0] <= root->val)
        		ans = false;
        	return {l[0], r[1]};
        }    
    }
};

or

class Solution {
    bool ans = true;
    long prevVal = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if(!root || ans == false)
            return true;
        isValidBST(root->left);
        if(root->val <= prevVal)
            ans = false;
        else
            prevVal = root->val;
        isValidBST(root->right);
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • LeetCode 965. 单值二叉树

    Michael阿明
  • LeetCode 222. 完全二叉树的节点个数(二分查找)

    说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底...

    Michael阿明
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • Golang Leetcode 450. Delete Node in a BST.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175007

    anakinsun
  • python中创建和遍历二叉树

    py3study
  • LeetCode 146 LRU Cache

    实现一个缓存机制。很多人的写法都是使用HashTable, Map,Dictionary 或者别的工具。

    ShenduCC
  • 利用rbd命令把 ceph pool 中的一个镜像导出

    查看镜像 [root@node1 ~]# rbd ls images a56330e7-79d7-4639-a68f-366ac344bfe2 eccfee07...

    院长技术
  • 浏览器环境检测

    本文是直接把seleniumpyppeteer 以及正常打开浏览器 的环境差异直接列出来

    爬虫

扫码关注云+社区

领取腾讯云代金券