问题描述:
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:
2 / \ 1 3
Binary tree [2,1,3]
, return true.
Example 2:
1 / \ 2 3
Binary tree [1,2,3]
, return false.
原问题链接:https://leetcode.com/problems/validate-binary-search-tree/
问题分析
最初想法
这个问题粗看的时候很简单,我们有一种递归的思路。就是对于里面每个节点,判断它如果有左右子节点的话,它的当前节点应该大于它的左子节点的值,如果有右子节点的话,应该小于它的右子节点的值。于是得到如下的实现代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { if(root == null || (root.left == null && root.right == null)) return true; if(root.left != null && root.left.val >= root.val) return false; if(root.right != null && root.right.val <= root.val) return false; return isValidBST(root.left) && isValidBST(root.right); } }
可是在实际执行的过程中却报错了,对于如下的输入来说:
[10,5,15,null,null,6,20]
它相当于是一棵如下的树:
在上图,我们虽然每个点都满足了它的左子节点比当前节点小,右子节点值比当前节点大,但是出现了一个节点15的左子节点小于根节点15的情况。这和前面二叉搜索树的定义有冲突。这是因为我们前面忽略了一个问题,在二叉搜索树里,一个节点比它的左子树的所有元素要大,比它右子树的所有元素要小。而这里仅仅根据一个节点和它的左右子节点的比较关系是不够的。
修改
于是,我们需要根据前面的情况进行修改。 在任何一个节点,我们需要定义这个节点所在的范围。因此需要引入两个变量,min, max。分别表示它所在的最大值和最小值。这样,对于任何一个节点来说,它的左子节点对应的值的范围是[min, node.val],就是从min到当前节点的值。而右子节点值对应的范围则是[node.val, max]。
于是我们就得到如下的代码:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValidBST(TreeNode node, int min, int max) { if(node == null) return true; return node.val > min && node.val < max && isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max); } }
可是我们运行的时候会发现居然出错了,导致错误结果的是如下的一组输入:
[2147483647]
这里的问题就在于,我们当前在递归里设定的初始值为Integer.MAX_VALUE, Integer.MIN_VALUE。它们相当于是两个边界值,而在问题里要求是一个节点的值和它的左右子节点不能是相等的关系。所以会出现还差一点的情况。
这里的问题就是在于我们初始设定了这么两个极端的值,但是如果正好某个节点的值就是这两个值的话,我们程序就会出问题。所以在代码里就不应该设定初始的最大和最小值。而且从最初的代码调用里,第一个检查的元素就是根节点,它取任意值都是合理的。所以我们只需要设定在后面的递归里逐步将当前的值作为最大或者最小值传递到后面的调用中来判断就好了。
详细的代码实现如下:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root,null,null); } private boolean isValidBST(TreeNode root, Integer max, Integer min){ if(root==null) return true; if(max !=null && root.val >= max) return false; if(min != null && root.val <= min) return false; return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val); } }
上面代码里不是利用原生的int类型,而是改为使用Integer类型的参数。这样在最开始的情况下,将最大值和最小值都设置为null,可以规避硬设定一个初始值的问题。
相关推荐
leetcode的题目:Balanced Binary Tree
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
leetcode ...Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
最终450 Love Babbar 450问题
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
leetcode LeetCode刷题 题号是LeetCode原题,题目是自己的解答 Easy 题号 题目 Tags Star Company HashMap :star: :star: :star: Integer :star: :star: String :star: String、Stack :star: :star: :star: ...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...