Valid Binary Search Tree

Question:

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
An example:

  2
 / \
1   4
   / \
  3   5
The above binary tree is serialized as {2,1,4,#,#,3,5} (in level order).

Lesson Learned:

• 似乎bst的题都会传进两个参数进行比较。此题的两个参数为max和min，当与左节点比较时，根节点变成了max；当与右节点比较时，根节点变成min。递归完成所有左右子树的比较。

• 限定的范围是跟它最邻近的左节点和右节点

• 传Integer.MAX和Integer.MIN进去确实可以找到最大的边界值，不用再想着如何去找min和max的初始值.
• 刚开始想再写一个recursion做最小值和最大值的判断，因为忽略了找左右子树的最值和左孩子小于root右孩子大于root其实是大问题小问题。
• 涉及和前一个val比较的问题--》queue

Code:

1. recursion

    /**
     * Definition of TreeNode:
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left, right;
     *     public TreeNode(int val) {
     *         this.val = val;
     *         this.left = this.right = null;
     *     }
     * }
     */
    public class Solution {
        /**
         * @param root: The root of binary tree.
         * @return: True if the binary tree is BST, or false
         */
        public boolean isValidBST(TreeNode root) {
            // write your code here
            return validBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
        private boolean validBSTHelper(TreeNode root, long min, long max) {
            if (root == null) {
                return true;
            }
            if (root.val <= min || root.val >= max) {
                return false;
            }
            return validBSTHelper(root.left, min, root.val) 
                && validBSTHelper(root.right, root.val, max);
        }
    }
   

2.inorder

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    // Inorder
    // 涉及和前一个val比较的问题--》queue
    private Queue<Integer> queue = new LinkedList<Integer>();

    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        queue.add(root.val);
        inorder(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        // 要调用装进queue的函数
        inorder(root);
        int pre = queue.poll();
        while (queue.peek() != null) {
            if (pre >= queue.peek()) {
                return false;
            }
            pre = queue.poll();
        }
        return true;
    }
}