Validate Binary Search Tree
题目:
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.
A single node tree is a BST
分析:
解法1是老方法,逻辑已经忘记了...
还有一种用result type的方法可以做好这道题
解法1:
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean ifReachedBottomLeft = false;
int prev = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
// write your code here
if (root == null) {
return true;
}
if (!isValidBST(root.left) ) {
return false;
}
// do something
if (ifReachedBottomLeft == true && prev >= root.val) {
return false;
}
ifReachedBottomLeft = true;
prev = root.val;
if (!isValidBST(root.right) ) {
return false;
}
return true;
}
}