Validate Binary Search Tree 95

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. 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).

Solution

用一个resulttype结构记录以某一节点为根的子树是否是bst以及其最大值和最小值。分：分别看左右子树是否为bst以及寻找其最大值和最小值。治：看左右子树是否都为bst并且左子树的最大值是否小于root的值，以及root的值是否小于右子树的最小值。

边界：当root＝＝null时，1）树的根节点为null，返回true，2）叶子节点的左右子树根节点为null，返回true，此时max值赋值为无穷小，min值赋值为无穷大，这样是因为最后一行比较root value和max，min时不会取到max和min的值

代码如下：

D & C:

/**
 * 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;
 *     }
 * }
 */
class ResultType{
    public boolean isBST;
    public int maxValue;
    public int minValue;

    public ResultType(boolean isBST, int maxValue, int minValue){
        this.isBST = isBST;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
} 

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
        ResultType r = validateHelper(root);
        return r.isBST;
    }

    public ResultType validateHelper(TreeNode root){
        if(root == null){
            return new ResultType(true, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        ResultType left = validateHelper(root.left);
        ResultType right = validateHelper(root.right);

        if(!left.isBST || !right.isBST){
            return new ResultType(false, 0, 0);
        }

        if((root.left != null && root.val <= left.maxValue) || (root.right !=null && root.val >= right.minValue)){
            return new ResultType(false, 0, 0);
        }

        return new ResultType(true, Math.max(root.val, right.maxValue), Math.min(root.val, left.minValue));
    }
}