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

给出一棵二叉树，判断是否符合给定的规则

思路：

考虑二叉树的中序遍历。

二叉树的中序遍历是升序的，因此中序遍历后判断序列是否是升序即可。

代码：

    public static boolean isValidBST(TreeNode root){
        if(root == null){
            return true;
        }
        Stack<TreeNode> ts = new Stack<TreeNode>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        TreeNode ptr = root;
        //中序遍历
        while(ptr != null || !ts.isEmpty()){
            while(ptr != null){
                ts.push(ptr);
                ptr = ptr.left;
            }

            if( !ts.isEmpty() ){
                ptr = ts.pop();
                arr.add(ptr.val);
                ptr = ptr.right;
            }
        }
        int index = 0;
        int[] arrs = new int[arr.size()];
        for(int i: arr){
            arrs[index++] = i;
        }
        //判断中序遍历得到的序列是否是升序的
        index = arrs[0];
        boolean flag = true;
        for(int i = 1; i < arr.size(); i++){
            if(index >= arrs[i]){
                flag = false;
                break;
            }
            index = arrs[i];
        }
        return flag;
    }

代码优化：

上述方法中，首先是将中序序列存储在集合中，为了判断升序方便又转换为数组，比较繁琐。

其实无需存储中序序列，在中序遍历过程中进行判断即可，一旦不符合升序条件就返回false。

代码：

    //代码优化(中序遍历过程中判断即可)
    public static boolean isValidBST(TreeNode root){
        if(root == null){
            return true;
        }
        Stack<TreeNode> ts = new Stack<TreeNode>();
        TreeNode ptr = root;
        TreeNode pre = null;
        //中序遍历
        while(ptr != null || !ts.isEmpty()){
            while(ptr != null){
                ts.push(ptr);
                ptr = ptr.left;
            }

            if( !ts.isEmpty() ){
                ptr = ts.pop();
                if( pre != null && pre.val >= ptr.val){
                    return false;
                }
                pre = ptr;
                ptr = ptr.right;
            }
        }
        return true;
        
    }

leetcode98 Validate Binary Search Tree

leetcode98 Validate Binary Search Tree

相关推荐