[LintCode] 95 Validate Binary Search Tree 解题报告

Description
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


Example
An example:

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


思路
用in-order traverse。每次用当前节点和左子树遍历过的最后一个节点做比较。如果最后一个节点的值小，就说明这不是一个BST。因为BST的任何一个节点比左边大。
注意程序先把最后一个左边的节点设为Integer.MIN，因为最最左边那个点没有再左边可以比，所以要先设一个最小值保证不会比这个最左边的节点大。
还需要设一个fristNode表示当前点是不是最最左边这个点。



Code

/**
 * 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
     */
    
    private int lastVal = Integer.MIN_VALUE;
    private boolean firstNode = true;
    
    public boolean isValidBST(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        
        if (!isValidBST(root.left)) {
            return false;
        }
        
        if (!firstNode && root.val <= lastVal) {
            return false;
        }
        
        firstNode = false;
        lastVal = root.val;
        
        if (!isValidBST(root.right)) {
            return false;
        }
        
        return true;
    }
}

解法二：
Divide & Conquer
个人觉得这个写法更棒


Code

/**
 * 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 helper(root, null, null);
    }
    
    public boolean helper(TreeNode root, Integer min, Integer max) {
        
        if (root == null) {
            return true;
        }
        
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
            return false;
        }
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}