力扣98、102、108
先放上原题链接：98，验证二叉搜索树，102，二叉树的层序遍历，108，转换有序数组为二叉搜索树。
首先是第98，验证二叉搜索树，先看看题目：
题目提供给了我们一个二叉树，需要我们来验证是不是搜索树（并没有要求需要平衡），关于二叉搜索树不了解的同学可以自行搜索。对于这道题，我的第一思路是，从下到上递归二叉树，然后得到子树的最大最小值，然后将当前节点和左右子树的最大最小值做对比。下面是我的代码，比较粗糙：
class Solution {
public boolean isValidBST(TreeNode root) {
int[] l=new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
int[] r=new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
boolean left ;
if (root.left!=null){
left=isValidBST2(root.left,l);
}else {
left=true;
}
boolean right ;
if (root.right!=null){
right=isValidBST2(root.right,r);
}else {
right=true;
}
int rrMin=Math.min(r[0],r[1]);
int llMax=Math.max(l[0],l[1]);
if (root.left!=null&&llMax>=root.val) {
left=false;
}
if (root.right!=null&&rrMin<=root.val) {
right=false;
}
return left && right ;
}
public boolean isValidBST2(TreeNode root,int[] m) {
if (root.left == null && root.right == null) {
m[0] = root.val;
m[1]=root.val;
return true;
}
int[] l=new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
int[] r=new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
boolean left ;
if (root.left!=null){
left=isValidBST2(root.left,l);
}else {
left=true;
}
boolean right ;
if (root.right!=null){
right=isValidBST2(root.right,r);
}else {
right=true;
}
m[0]=Math.min(m[0],root.val);
int llMin;
if (root.left!=null){
llMin=Math.min(l[0],l[1]);
}else {
llMin=root.val;
}
int rrMin;
if (root.right!=null){
rrMin=Math.min(r[0],r[1]);
}else {
rrMin=root.val;
}
int min=Math.min(llMin,rrMin);
m[0]=Math.min(m[0],min);
m[1]=Math.max(m[1],root.val);
int llMax;
if (root.left!=null){
llMax=Math.max(l[0],l[1]);
}else {
llMax=root.val;
}
int rrMax;
if (root.right!=null){
rrMax=Math.max(r[0],r[1]);
}else {
rrMax=root.val;
}
int max=Math.max(llMax,rrMax);
m[1]=Math.max(m[1],max);
if (root.left!=null&&llMax>=root.val) {
left=false;
}
if (root.right!=null&&rrMin<=root.val) {
left=false;
}
return left && right ;
}
}
虽然代码比较长，但是其实比较好理解，其中重复的和可修剪的代码比较多。这段代码的时间复杂度是O(n)，空间复杂度也是O(n)，因为递归的深度可能会达到n。提交后发现使用了1ms，只击败了百分之30左右的用户。最后还是去看了官方解答，官方解答给出了两个，一个是从上至下递归查看是否满足条件，另外一个是中序遍历，看看遍历的结果是不是递增的，这个方法我觉得比较巧妙，并且实现又简单，详细可以去原链接看看，这里不给出代码了。
接下来是第102，二叉树的层序遍历，题目如下：
这题属于简单题，虽然官方定为中等，不过那是给基础比较薄弱或者没有接触过二叉树遍历的同学的定级，不然可以直接秒，下面是我的代码：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root==null) {
return List.of();
}
List<List<Integer>> res = new ArrayList<>();
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
ArrayDeque<TreeNode> deque2 = new ArrayDeque<>();
deque.addLast(root);
while (!deque.isEmpty()) {
List<Integer> list = new ArrayList<>();
while (!deque.isEmpty()){
TreeNode treeNode = deque.removeFirst();
if (treeNode.left != null) {
deque2.add(treeNode.left);
}
if (treeNode.right != null) {
deque2.add(treeNode.right);
}
list.add(treeNode.val);
}
res.add(list);
ArrayDeque<TreeNode> temp=deque2;
deque2=deque;
deque=temp;
}
return res;
}
}
我的实现和官方不太一样，官方使用一个队列来存储节点，然后再存储每一层的节点数来达到要求。我使用两个队列，一个队列存储当前层，一个存储下一层，这样实现我觉得更清晰一些。并且时间复杂度和空间复杂度其实是一样的。
最后是第108，转换有序数组为二叉搜索树，题目如下：
这题官方定为简单题，其实我感觉不太简单。如果按照平衡树来做，那就比较复杂了，平衡树旋转的代码可能大部分人都不太会（包括我，所以我准备找个时间好好学一下这些经典算法，以前学了忘了）。于是我直接看官方解答了，官方解答的方法很巧妙，他直接从数组的中间选择一个数作为根节点，然后递归的构建左右子树，这样就保证了树的平衡性。下面是我根据这个思路自己实现的代码：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
TreeNode root = new TreeNode(nums[len / 2]);
root.left = sortedArrayToBST2(nums, 0, len / 2 - 1);
root.right = sortedArrayToBST2(nums, len / 2 + 1, len - 1);
return root;
}
public TreeNode sortedArrayToBST2(int[] nums, int start, int end) {
if (start > end) {
return null;
}
if (start == end) {
return new TreeNode(nums[start]);
}
int rootIndex = (start + end) / 2;
TreeNode root = new TreeNode(nums[rootIndex]);
root.left = sortedArrayToBST2(nums, start, rootIndex - 1);
root.right = sortedArrayToBST2(nums, rootIndex + 1, end);
return root;
}
}
这题思路其实我觉得不太容易想到，我看了一下解答下的大家的评论，都认为这题比较巧妙，并且也有小伙伴试了平衡树，结果会超时。