Wednesday, March 20, 2013

Validate Binary Search Tree

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.

make an inorder traversal, if the value is increasing, it is a BST.

 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
public class Solution {
    private TreeNode pre;
    private boolean ret;
    void inorder(TreeNode root){
        if(ret == false) return;
        if(root==null) return;
        if(pre == null){ pre = root;}
            if(pre.val >= root.val){
                ret = false;
            pre = root;
        if(ret) inorder(root.right);
    public boolean isValidBST(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        pre = null;
        ret = true;
        return ret;

No comments:

Post a Comment

Manacher's Longest Palindromic Substring Algorithm