LeetCode - Validate Binary Search Tree
发布时间:2020-12-14 04:50:03 所属栏目:大数据 来源:网络整理
导读: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
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: 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. 如果对BST 中序遍历, 会产生有序数列。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //BST inorder traverse will generate a ordered sequnence public boolean isValidBST(TreeNode root) { if(root == null){ return true; } List<Integer> list = new ArrayList<>(); list.add(null); return helper(root,list); } public boolean helper(TreeNode node,List<Integer> list){ if(node == null){ return true; } boolean left = helper(node.left,list); if(list.get(list.size()-1) != null && node.val <= list.get(list.size()-1)){ return false; } list.add(node.val); boolean right = helper(node.right,list); return left && right; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |