[LeetCode] 98. 验证二叉搜索树
发布时间:2020-12-14 04:43:33 所属栏目:大数据 来源:网络整理
导读:题目链接 : https://leetcode-cn.com/problems/validate-binary-search-tree/ 题目描述: 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数
题目链接 : https://leetcode-cn.com/problems/validate-binary-search-tree/ 题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征:
示例:示例 1: 输入: 2 / 1 3 输出: true 示例 2: 输入: 5 / 1 4 / 3 6 输出: false 解释: 输入为: [5,1,4,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。 思路:因为二叉搜索树中序遍历是递增的,所以我们可以中序遍历判断前一数是否小于后一个数. # Definition for a binary tree node. # class TreeNode: # def __init__(self,x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self,root: TreeNode) -> bool: res = [] def helper(root): if not root: return helper(root.left) res.append(root.val) helper(root.right) helper(root) return res == sorted(res) and len(set(res)) == len(res) 思路一:迭代 我们可以通过中序遍历迭代方式94. 二叉树的中序遍历来判断. 思路二:递归
代码:迭代 # Definition for a binary tree node. # class TreeNode: # def __init__(self,root: TreeNode) -> bool: stack = [] p = root pre = None while p or stack: while p: stack.append(p) p = p.left p = stack.pop() if pre and p.val <= pre.val: return False pre = p p = p.right return True 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) { Deque<TreeNode> stack = new LinkedList<>(); TreeNode p = root; TreeNode pre = null; while (p != null || !stack.isEmpty()) { while (p != null) { stack.push(p); p = p.left; } p = stack.pop(); if (pre != null && pre.val >= p.val) return false; pre = p; p = p.right; } return true; } } 思路二 利用递归中序遍历 # Definition for a binary tree node. # class TreeNode: # def __init__(self,root: TreeNode) -> bool: self.pre = None def isBST(root): if not root: return True if not isBST(root.left): return False if self.pre and self.pre.val >= root.val: return False self.pre = root #print(root.val) return isBST(root.right) return isBST(root) java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { TreeNode pre = null; public boolean isValidBST(TreeNode root) { if (root == null) return true; if (!isValidBST(root.left)) return false; if (pre != null && pre.val >= root.val) return false; pre = root; return isValidBST(root.right); } } 利用最大值最小值 # Definition for a binary tree node. # class TreeNode: # def __init__(self,root: TreeNode) -> bool: def isBST(root,min_val,max_val): if root == None: return True # print(root.val) if root.val >= max_val or root.val <= min_val: return False return isBST(root.left,root.val) and isBST(root.right,root.val,max_val) return isBST(root,float("-inf"),float("inf")) 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 isBST(root,Long.MAX_VALUE,Long.MIN_VALUE); } private boolean isBST(TreeNode root,long maxValue,long minValue) { if (root == null) return true; if (root.val >= maxValue || root.val <= minValue) return false; return isBST(root.left,minValue) && isBST(root.right,maxValue,root.val); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |