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.
Solution 1:
//相当于中序遍历，先加入中间节点，再加入左节点，再加入右节点
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
Stack<TreeNode> s = new Stack<>();
TreeNode pre = null;
s.push(root);
while (!s.isEmpty()) {
TreeNode tn = s.peek();
while (tn != null) {
tn = tn.left;
s.push(tn);
}
s.pop();
if (!s.isEmpty()) {
tn = s.pop();
if (pre != null && tn.val <= pre.val)
return false;
pre = tn;
s.push(tn.right);
}
}
return true;
}
}
Solution 2://必须是Long类型，例如只有有个2^31-1节点，如果把Long改成Integer，则会报错
class Solution {
Integer prev = null;
boolean isValid = true;
public boolean isValidBST(TreeNode root) {
helper(root);
return isValid;
}
private void helper(TreeNode root) {
if (root == null)
return;
if (isValid == false)
return;
helper(root.left);
if (prev != null) {
if (root.val <= prev)
isValid = false;
}
prev = root.val;
helper(root.right);
}
}
98. Validate Binary Search Tree
原文：https://www.cnblogs.com/MarkLeeBYR/p/10537213.html
