“验证二叉搜索树”的版本间的差异
来自qingwei personal wiki
（创建页面，内容为“== 描述 == === leetcode === https://leetcode-cn.com/problems/validate-binary-search-tree/description/<br /> https://leetcode.com/problems/validate-binary-search-tr…”） |
|||
| 第31行： | 第31行： | ||
根节点的值为 5 ，但是其右子节点值为 4 。 | 根节点的值为 5 ，但是其右子节点值为 4 。 | ||
</pre> | </pre> | ||
| − | + | == 递归 == | |
| + | <source lang="java"> | ||
| + | /** | ||
| + | * Definition for a binary tree node. | ||
| + | * public class TreeNode { | ||
| + | * int val; | ||
| + | * TreeNode left; | ||
| + | * TreeNode right; | ||
| + | * TreeNode(int x) { val = x; } | ||
| + | * } | ||
| + | */ | ||
| + | class Solution { | ||
| + | public boolean isValidBST(TreeNode root) { | ||
| + | return isValid(root, null, null); | ||
| + | } | ||
| + | |||
| + | private boolean isValid(TreeNode node, Integer min, Integer max) { | ||
| + | if (node == null) { | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | if (left != null && min >= node.val) { | ||
| + | return false; | ||
| + | } | ||
| + | if (right != null && max <= node.val) { | ||
| + | return false; | ||
| + | } | ||
| + | return isValid(node.left, min, node.val) && isValid(node.right, node.val, max); | ||
| + | } | ||
| + | } | ||
| + | </source> | ||
[[category: 算法]] | [[category: 算法]] | ||
[[category: leetcode]] | [[category: leetcode]] | ||
[[category: 树]] | [[category: 树]] | ||
2018年6月3日 (日) 08:43的版本
描述
leetcode
https://leetcode-cn.com/problems/validate-binary-search-tree/description/
https://leetcode.com/problems/validate-binary-search-tree/description/
问题
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
private boolean isValid(TreeNode node, Integer min, Integer max) {
if (node == null) {
return true;
}
if (left != null && min >= node.val) {
return false;
}
if (right != null && max <= node.val) {
return false;
}
return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
}
}
