首页 > 代码库 > Leetcode-Validate BST

Leetcode-Validate BST

2024-08-01 02:41:26   222人阅读

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

WRONG solution:

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public boolean isValidBST(TreeNode root) {12         if (root==null)13             return true;14         15         return isValidBSTRecur(root);16     }17     18     public boolean isValidBSTRecur(TreeNode curNode){19         if (curNode.left==null&&curNode.right==null)20             return true;21         22         boolean leftValid=true;23         boolean rightValid=true;24         25         if (curNode.left!=null){26             if (curNode.left.val>=curNode.val)27                 return false;28             leftValid = isValidBSTRecur(curNode.left);29         }30         31         if (curNode.right!=null){32             if (curNode.right.val<=curNode.val)33                 return false;34             rightValid = isValidBSTRecur(curNode.right);35         }36         37         if (leftValid&&rightValid)38             return true;39         else40             return false;41     }42 }

This is wrong! Because we only consider about one level up! Example:

Input:{10,5,15,#,#,6,20}
Output:true
Expected:false

Correct Solution:

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public boolean isValidBST(TreeNode root) {12         if (root==null)13             return true;14         15         List<Integer> queue = new ArrayList<Integer>();16         isValidBSTRecur(root,queue);17         18         for (int i=1;i<queue.size();i++)19             if (queue.get(i)<=queue.get(i-1))20                 return false;21         22         return true;23     }24     25     public void isValidBSTRecur(TreeNode curNode, List<Integer> queue){26         if (curNode.left==null&&curNode.right==null){27             queue.add(curNode.val);28             return;29         }30             31         32         if (curNode.left!=null)33             isValidBSTRecur(curNode.left,queue);34         queue.add(curNode.val);35         if (curNode.right!=null)36             isValidBSTRecur(curNode.right,queue);37         38         return;39     }40 }

We put nodes into a list in the preorder, then check whether the list is monotonic increasing.

Leetcode-Validate BST


联系
我们