[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树

发布时间：2020-12-14 03:45:12 所属栏目：大数据来源：网络整理

导读：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 node

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.

解法1: 递归Recursive

解法2：迭代Iterative

Java:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean valid(TreeNode root,long low,long high) {
        if (root == null) return true;
        if (root.val <= low || root.val >= high) return false;
        return valid(root.left,low,root.val) && valid(root.right,root.val,high);
    }
}

Java:

public boolean isValidBST(TreeNode root) {
    if(root==null)
        return true;
 
    return helper(root,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
}
 
public boolean helper(TreeNode root,double low,double high){
 
    if(root.val<=low || root.val>=high)
        return false;
 
    if(root.left!=null && !helper(root.left,root.val)){
        return false;
    }
 
    if(root.right!=null && !helper(root.right,high)){
        return false;
    }
 
    return true;    
}

Java: Iterative

public boolean isValidBST(TreeNode root) {
   if (root == null) return true;
   Stack<TreeNode> stack = new Stack<>();
   TreeNode pre = null;
   while (root != null || !stack.isEmpty()) {
      while (root != null) {
         stack.push(root);
         root = root.left;
      }
      root = stack.pop();
      if(pre != null && root.val <= pre.val) return false;
      pre = root;
      root = root.right;
   }
   return true;
}

Java: Iterative

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
 
        LinkedList<BNode> queue = new LinkedList<BNode>();
        queue.add(new BNode(root,Double.POSITIVE_INFINITY));
        while(!queue.isEmpty()){
            BNode b = queue.poll();
            if(b.n.val <= b.left || b.n.val >=b.right){
                return false;
            }
            if(b.n.left!=null){
                queue.offer(new BNode(b.n.left,b.left,b.n.val));
            }
            if(b.n.right!=null){
                queue.offer(new BNode(b.n.right,b.n.val,b.right));
            }
        }
        return true;
    }
}
//define a BNode class with TreeNode and it‘s boundaries
class BNode{
    TreeNode n;
    double left;
    double right;
    public BNode(TreeNode n,double left,double right){
        this.n = n;
        this.left = left;
        this.right = right;
    }
}

Python: wo

class Solution(object):
    def isValidBST(self,root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        return self.helper(root,float(‘-inf‘),float(‘inf‘))
        
    def helper(self,root,mi,mx):   
        if not root:
            return True
        
        if root.val >= mx or root.val <= mi:
            return False
            
        return self.helper(root.left,root.val) and self.helper(root.right,mx)

Python:

# Morris Traversal Solution
class Solution:
    # @param root,a tree node
    # @return a list of integers
    def isValidBST(self,root):
        prev,cur = None,root
        while cur:
            if cur.left is None:
                if prev and prev.val >= cur.val:
                    return False
                prev = cur
                cur = cur.right
            else:
                node = cur.left
                while node.right and node.right != cur:
                    node = node.right

                if node.right is None:
                    node.right = cur
                    cur = cur.left
                else:
                    if prev and prev.val >= cur.val:
                        return False
                    node.right = None
                    prev = cur
                    cur = cur.right

        return True

C++:

// Recursion without inorder traversal
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return isValidBST(root,LONG_MIN,LONG_MAX);
    }
    bool isValidBST(TreeNode *root,long mn,long mx) {
        if (!root) return true;
        if (root->val <= mn || root->val >= mx) return false;
        return isValidBST(root->left,mn,root->val) && isValidBST(root->right,root->val,mx);
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!