Java for LeetCode 098 Validate Binary Search Tree

浏览数：48 / 时间：2015年06月08日

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.

解题思路：

本题方法多多，可以采用DFS，当然最简答的方法是采用之前的中序遍历Java for LeetCode 094 Binary Tree Inorder Traversal检查得到的List是否有序即可。

    public boolean isValidBST(TreeNode root) {

        List<Integer> list=inorderTraversal(root);
        if(list.size()==0)
            return true;
        int temp=list.get(0);
        for(int i=1;i<list.size();i++){
        	if(temp>=list.get(i))
        		return false;
        	temp=list.get(i);
        }
        return true;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    if(root==null)
        return list;
    if (root.left != null)
        list.addAll(inorderTraversal(root.left));
    list.add(root.val);
    if (root.right != null)
        list.addAll(inorderTraversal(root.right));
    return list;
    }

JAVA实现如下：

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 098 Validate Binary Search Tree