98. Validate Binary Search Tree - Medium
发布时间:2020-12-14 05:17:42 所属栏目:大数据 来源:网络整理
导读: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 node
Given a binary tree,determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:
Example 1: Input: 2 / 1 3 Output: true Example 2: 5 / 1 4 ? / ? 3 6 Output: false Explanation: The input is: [5,1,4,null,3,6]. The root node‘s value ? is 5 but its right child‘s value is 4. ? recursion 给每个节点定义一个区间,如果节点的值落在区间外,返回false,否则继续递归左右节点,区间上下限相应调整 注意!!min,max如果用int会溢出,要用long time: O(n),space: O(n) /** * 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,Long.MIN_VALUE,Long.MAX_VALUE); } public boolean isValid(TreeNode node,long min,long max) { if(node == null) { return true; } if(node.val <= min || node.val >= max) { return false; } return isValid(node.left,min,node.val) && isValid(node.right,node.val,max); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |