lintcode：验证二叉查找树

题目

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

节点的左子树中的值要严格小于该节点的值。

节点的右子树中的值要严格大于该节点的值。

左右子树也必须是二叉查找树。

一个节点的树也是二叉查找树。

解题

二叉查找树中序遍历是升序，可以中序遍历后，根据是否升序判断是否是二叉查找树，这样效率不高

在LeetCode中看到的下面的方法

根据结点满足值得范围进行查找

初始的时候只有一个根结点，范围minval，maxval都应该为null

随着迭代的运行更新minval、maxval

下面就看代码吧

/**

 * 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) {

            return isValid(root,null,null);

    }

    public boolean isValid(TreeNode root,Integer minVal,Integer maxVal){

        if(root == null)

            return true;

        if((minVal == null ||root.val> minVal) && (maxVal ==null ||root.val< maxVal)){

            return isValid(root.left,minVal,root.val)

                && isValid(root.right,root.val,maxVal);

        }

        return false;

    }

}

巴特西

lintcode：验证二叉查找树

最新文章

热门文章