力扣爆刷第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);
    }

}