力扣爆刷第91天之hot100五连刷41-45

力扣爆刷第91天之hot100五连刷41-45

一、102. 二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-100-liked
思路：层序遍历是典型题目，使用队列，然后将队列的size作为每一层的元素个数。

class Solution {List<List<Integer>> arrayList = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {if(root == null) return arrayList;Deque<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {int len = queue.size();List<Integer> list = new ArrayList<>();for(int i = 0; i < len; i++) {TreeNode t = queue.poll();list.add(t.val);if(t.left != null) queue.add(t.left);if(t.right != null) queue.add(t.right);}arrayList.add(list);}return arrayList;}
}

二、108. 将有序数组转换为二叉搜索树

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
思路：要将有序数组转换成二叉搜索树，直接使用二分法遍历数组，在此过程中创建二叉树即可。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return bst(nums, 0, nums.length-1);}TreeNode bst(int[] nums, int left, int right) {if(left > right) return null;int mid = left + (right-left)/2;TreeNode root = new TreeNode(nums[mid]);root.left = bst(nums, left, mid-1);root.right = bst(nums, mid+1, right);return root;}
}

三、98. 验证二叉搜索树

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
思路：验证二搜索树，应该使用前序遍历，然后向下遍历的过程中要携带父节点的信息。

class Solution {public boolean isValidBST(TreeNode root) {return isTrue(root, null, null);}boolean isTrue(TreeNode root, TreeNode min, TreeNode max) {if(root == null) return true;if(min != null && root.val <= min.val) return false;if(max != null && root.val >= max.val) return false;return isTrue(root.left, min, root) && isTrue(root.right, root, max); }
}

四、230. 二叉搜索树中第K小的元素

题目链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked
思路：求第k小的元素要利用二叉搜索树的特性，中序遍历后便是递增序列，所以中序遍历计数即可。

class Solution {int v = 0, i = 0;public int kthSmallest(TreeNode root, int k) {reverse(root, k);return v;}void reverse(TreeNode root, int k) {if(root == null) return ;reverse(root.left, k);i++;if(i == k) {v = root.val;}reverse(root.right, k);}
}

五、199. 二叉树的右视图

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-100-liked
思路：求自上而下的右视图，很简单，采用前序遍历的方法，但是先遍历右子树再遍历左子树，然后用一个全局变量记录深度，每次深度增加才会记录元素。

class Solution {List<Integer> list = new ArrayList<>();int deep = 0;public List<Integer> rightSideView(TreeNode root) {reverse(root, 1);return list;}void reverse(TreeNode root, int i) {if(root == null) return ;if(i > deep) {deep = i;list.add(root.val);}reverse(root.right, i+1);reverse(root.left, i+1);}}