首页 > 代码库 > Validate Binary Search Tree,判断是否是二叉排序树

Validate Binary Search Tree,判断是否是二叉排序树

算法分析:两种方法,一种是中序遍历,然后得到一个序列,看序列是否是有序的。第二种,是用递归。

中序遍历:

public class Solution {    List<Integer> list = new ArrayList<>();    public boolean isValidBST(TreeNode root) {        if(root == null)        {            return true;        }        inorderTraversal(root);        for(int i = 0; i < list.size() - 1; i ++)        {            if(list.get(i) >= list.get(i+1))            {                return false;            }        }        return true;    }    public void inorderTraversal(TreeNode root)    {        if(root == null)        {            return ;        }        inorderTraversal(root.left);        list.add(root.val);        inorderTraversal(root.right);    }}

 递归:

public class Solution {    List<Integer> list = new ArrayList<>();    public boolean isValidBST(TreeNode root) {        if(root == null)        {            return true;        }        inorderTraversal(root);        for(int i = 0; i < list.size() - 1; i ++)        {            if(list.get(i) >= list.get(i+1))            {                return false;            }        }        return true;    }    public void inorderTraversal(TreeNode root)    {        if(root == null)        {            return ;        }        inorderTraversal(root.left);        list.add(root.val);        inorderTraversal(root.right);    }}

 

Validate Binary Search Tree,判断是否是二叉排序树