本文共 2247 字,大约阅读时间需要 7 分钟。
给定一棵二叉树,判断该二叉树是否为BST(搜索二叉树)
对二叉树进行中序遍历,得到中序遍历序列。如果中序遍历序列是严格递增,则二叉树BST。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean isValidBST(TreeNode root) { if (root == null) return true; Listlist = new ArrayList<>(); inOrder(root, list); Integer[] array = new Integer[list.size()]; list.toArray(array); int i = 1; while (i < array.length) { if (array[i] <= array[i - 1]) break; i++; } return i == array.length; } // 获取中序遍历序列 如果中序遍历序列为递增序列 则为BST public void inOrder(TreeNode root, List list) { if (root == null) return ; inOrder(root.left, list); list.add(root.val); inOrder(root.right, list); }}
效率比较低的原因是其空间复杂度为O(n),另外还有就是判断是否有序时需要遍历整个序列。
之后尝试了对代码进行改进,发现可以不使用list存储变量,这样空间复杂度便降下来了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { int pre = Integer.MIN_VALUE; boolean t = true, start = false; // start用于判断当前节点是否为中序变量的第一个节点 t用于判断是否有序 public boolean isValidBST(TreeNode root) { if (root == null) return true; inOrder(root); return t; } // 获取中序遍历序列 如果中序遍历序列为递增序列 则为BST public void inOrder(TreeNode root) { if (root == null) return ; inOrder(root.left); if (!start) { pre = root.val; start = true; } else { t = t && root.val > pre; pre = root.val; } inOrder(root.right); }}
class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBST(TreeNode root, long minVal, long maxVal) { if (root == null) return true; if (root.val >= maxVal || root.val <= minVal) return false; return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal); }}
转载地址:http://ltesi.baihongyu.com/