Validate Binary Search Tree

本文主要是介绍Validate Binary Search Tree，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Code link: https://leetcode.com/problems/validate-binary-search-tree/

Constraint:

• The number of nodes in the tree is in the range [1, 104].
• -2^31 <= Node.val <= 2^31 - 1

Idea

For each node, we will need to check if its value is within certain range [min, max]. As we traverse downward, we have to update the range accordingly. Basically we need to update the upper bound when we go left and lower bound when we go right. Initially the range could be [-2^31 , 2^31 - 1]

• Attemp 1.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidBSTHelper(TreeNode root, int min, int max) {
        if (root == null) {
            return true;
        }
        
        if (root.val <= min || root.val >= max) {
            return false;
        }
        
        return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
    }
}

This solution doesn't work for the case where a node contains the the value of (2^31 - 1) or (-2^31). For example given the case [2147483647], the output would be false where it should be true.

• Attemp 2 Recursive solution
  A nice for BST is that if we inspect its values with in-order way, it is an ascending sequence. With that in mind, we can first do an in-order traversal and keep track of all the values in this order. Then we just need to verify whether the numbers are monotonously increasing or not.

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> inOrderPath = new ArrayList<>();
        isValidBSTHelper(root, inOrderPath);
        for (int i = 1; i < inOrderPath.size(); i++) {
            if (inOrderPath.get(i) <= inOrderPath.get(i - 1)) {
                return false;
            }
        }
        
        return true;
    }
    
    private void isValidBSTHelper(TreeNode root, List<Integer> inOrderPath) {
        if (root == null) {
            return;
        }
        
        isValidBSTHelper(root.left, inOrderPath);
        inOrderPath.add(root.val);
        isValidBSTHelper(root.right, inOrderPath);
    }
}

• Time: O(n) as in-order traversing and inspecting the list both take O(n).

• Space: O(n). Both recursion stack and the list take O(n).

• Attemp 3 Iterative solution:

class Solution {
   public boolean isValidBST(TreeNode root) {
       List<Integer> path = new ArrayList<>();
       TreeNode cur = root;
       Stack<TreeNode> st = new Stack<>();
       while (cur != null || !st.isEmpty()) {
           if (cur != null) {
               st.push(cur);
               cur = cur.left;
           } else {
               cur = st.pop();
               path.add(cur.val);
               cur = cur.right;
           }
       }
       
       for (int i = 1; i < path.size(); i++) {
           if (path.get(i) <= path.get(i - 1)) {
               return false;
           }
       }
       
       return true;
   }
}

• Time: O(n)
• Space: O(n) as both the stack and list has size up to n.
  Potenailly we could check for number sequence while traversing the tree, instead of checking it in later run:

				...
                if (path.size() > 0 && path.get(path.size() - 1) >= cur.val) {
                   return false;
               }
   			...

这篇关于Validate Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！