98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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:
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null){
return true;
}
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private static boolean helper(TreeNode root, long min, long max){
if (root == null){
return true;
}
if (root.val <= min || root.val >= max){
return false;
}
return helper(root.left,min, root.val) && helper(root.right,root.val, max);
}
}
// Long has been taken and it will work because node values are between Integer.MAX_VALUE and Integer.MIN_VALUE and Long has broader range than Integer
// TC: O(n)
// SC: O(n)
/*
Time complexity : O(N)\mathcal{O}(N)O(N) since we visit each node exactly once.
Space complexity : O(N)\mathcal{O}(N)O(N) since we keep up to the entire tree.
*/
Binary Search Tree
经典例题1: How to determine a binary tree is a BST?
10 == root
/ \
5 15
/ \ / \
2 7 12 20 <- all leaf node's level == 3
/ \
null null
Solution 0: in Order (very bad)
Step 1: Do Inorder traversal on the tree and store all the value in a arrayList
Step 2: check if array[i] < array[i+1]
Solution 1: in Order better
do not store all values just store one variable -> prevNode
for every node we traversal in ignorer:
check if curValue > prevValue
Time = O(n)
所有的点都要过一遍
Solution 2(Another way)
[min, max] 这个subtree的值都应当落在这个range里
BST: 左子树的最大值 < root'value
右子树的最小值 > root'value
10 == root \((-\infty,\infty)\)
/ \
\((-\infty,10)\) 5 15 \((10, +\infty)\)
/ \ / \
\((-\infty,5)\) 2 7 (5, 10) (10, 15)12 20 \((15,\infty)\)
/ \
null null
若5变为11则直接return false, 这边就不需要所有n都过一遍, 提前return false
往左走的时候, min不变, max变为当前层的rootvalue
往右走的时候, max不变, min变为当前层的rootvalue
publlic boolean isBST(TreeNode root, int max, int min){
if (root == null) return true;
// 检查当前层的root 在不在范围里
if (root.key <= min || root.key > max){
return false;
}
return isBST(root.left, root.key, min) && isBST(root.right, max, root.key)
}
Time: O(n)
Space: O(height)
1
\
3
\
5
这个是个binary search tree 但它不balance
Discussion
Recursion在tree题目基本应用大致分为2类用法
- 把value从上往下传递then从下往上的题目
1.1 BST判定方法
- 只把value从下往上传递 (更为常见, 必须熟练掌握)
2.1. getHeight(Node root) 是经典的把Integer value从下往上传递的题目
2.2. isBalanced(Node root) 是把boolean value从下往上传递的题目
2.3. isSymmetric(Node root1, Node root2)是把boolean value从下往上传送的题目
2.4. Assign the value of each node to be the total number of nodes that belong to its left subtree (是把integer value 从下往上传递的题目)