快乐的LeetCode --- 面试题 04.05. 合法二叉搜索树

ゝ一纸荒年。 2023-02-20 02:14 83阅读 0赞

**题目描述：**

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

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

**示例 2:**

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

--------------------

**解题思路1:**

[C++解法][C]：给出节点的范围如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]

--------------------

**代码1：**

class Solution {
        
    public:
        bool isValidBST(TreeNode* root) {
        
            return dfs(root, INT_MIN, INT_MAX);
        }
        bool dfs(TreeNode *root, long long minv, long long maxv){
        
            if(!root) return true;
            if(root-> val < minv || root -> val > maxv) return false;
    
            return dfs(root -> left, minv, root -> val -1ll)&&dfs(root -> right, root -> val +1ll, maxv); //其中，1ll是long long 类型的1，防止 -oo - 1溢出
        }
    };

--------------------

**解题思路2:**

二叉树的中序遍历一定是个递增的数列，且无重复元素

--------------------

**代码2：**

class Solution(object):
        def isValidBST(self, root):
            nodes =[]
            def search(root):
                if root:
                    search(root.left)
                    nodes.append(root.val)
                    search(root.right)
            search(root)
            return nodes == sorted(set(nodes))

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/legal-binary-search-tree-lcci][https_leetcode-cn.com_problems_legal-binary-search-tree-lcci]

[C]: https://www.bilibili.com/video/BV19t411w7Ep?from=search&seid=9107389073727276699
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621214837228.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70
[https_leetcode-cn.com_problems_legal-binary-search-tree-lcci]: https://leetcode-cn.com/problems/legal-binary-search-tree-lcci