力扣每日一题

algo›problem

About 3101 wordsAbout 10 min

algoleetcode-daily-question

2024-02-15

记录力扣中每日一题的解法，有的时候题目简单，有的时候题目困难，看自己时间充裕情况；

107. 二叉树的层序遍历 II （20240215更新）

二叉树的层级遍历，使用BFS来处理，只不过这个题目返回从底向上的节点，这点与普通的层级遍历有一点不一样。

我们在遍历每一层的时候，可以使用api把每一层值放到最前面。

如果不清楚具体使用的api，也可以正常存放，最后的时候将结果位置交换一下也是可以的。

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 上一题是从上往下，这题是从下往上
        // 从上往下 然后倒序输出？
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            // 每层的元素
            List<Integer> level = new LinkedList<>();
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode node = q.poll();
                level.add(node.val);

                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            } 
            // res.add(level);
            res.addFirst(level);
        }
        // 将元素进行交换
        // int len = res.size();
        // int left=0, right=len-1;
        // while(left<right){
        //     Collections.swap(res, left, right);
        //     left++;
        //     right--;
        // }
        // return res;
    }
}

var levelOrderBottom = function(root) {
    let res = [];
    if(root == null){
        return res;
    }
    let q = [];
    q.push(root);
    while(q.length>0){
        let sz = q.length;
        let level = [];
        for(let i=0;i<sz;i++){
            let cur = q.shift();
            level.push(cur.val);
            if(cur.left!=null){
                q.push(cur.left);
            }
            if(cur.right!=null){
                q.push(cur.right);
            }
        }
        res.unshift(level); // 在数组开头添加元素
    }
    return res;

};

简单知识点

1、java中向数组第一个位置插入元素nums.addFirst(val);

2、java中队列的api

Queue<Integre> q = new LinkedList<>();
q.offer(val);  // 添加元素
q.poll(); // 获取队列第一个元素，并删除
q.isEmpty(); // 判断队列是否为空

3、java中获取list的长度用size()方法，获取数组的长度用length属性

4、js中数组操作api

let nums = [2,9 ,5];
nums.pop();  // 删除最后一个元素
nums.unshift(val);  // 将一个或多个元素添加到数组开头，并返回新数组的长度。
nums.shift();  // 删除数组第一个元素，并返回该元素的值，改变数组的长度

103. 二叉树的锯齿形层序遍历（20240216更新）

给你二叉树的根节点root，返回节点值的锯齿型层序遍历。（即先从往右，下一层在从优往左）

这个还是基于BFS来，我们只需要新建一个变量，来表示方向。

Java

class Solution {
    boolean direct = true;  // 为true是向右， false向左
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new LinkedList<>();
            // 判断方向
            for(int i=0;i<size;i++){
                TreeNode node = q.poll();
                // 实现 z 字形遍历
                if(direct){
                    level.addLast(node.val);
                }
                else{
                    level.addFirst(node.val);
                }
                if(node.left !=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            res.add(level);
            direct = !direct;  // 切换方向
        }
        return res;
    }
}

429. N 叉树的层序遍历（20240217更新）

给定一个N叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）
树的序列输入使用层序遍历，每组子节点都由null值分割

层序遍历的话，我们还是需要再BFS的基础上来实现，我们需要再push到队列的时候循环节点的所有的子节点。

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }

        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            List<Integer> level = new LinkedList<>();
            int size = q.size();
            for(int i=0;i<size;i++){
                Node node = q.poll();  // 先从队列中取出节点，放入到List中
                level.add(node.val);

                List<Node> children = node.children;
                for(Node t: children){
                    q.offer(t);
                }
            }
            res.add(level);
        }
        return res;
    }
}

589. N 叉树的前序遍历（20240218更新）

给定一个n叉树的根节点root，返回其节点的前序遍历

我们参考二叉树的前序遍历方式，定义traverse函数用来递归，在遍历左右子节点的时候换成遍历root的所有子节点。

class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        traverse(root);
        return res;
    }
    public void traverse(Node root){
        if(root == null){
            return;
        }
        res.add(root.val);
        for(Node node: root.children){
            traverse(node);
        }
    }
}

590. N 叉树的后序遍历（20240219更新）

今天还是n叉树的遍历，还是利用二叉树的后序遍历来解这个题。

定义一个traverse的递归函数，先遍历子节点，最后在把当前节点的值存下来。

关于树的问题，需要思考了两个问题，一个就是每个节点需要做什么工作？二就是在什么时候做？

比如这道题，1就是每个节点需要将值放到对应的容器里面，2就是在遍历完之后，最后才放到容器里面。

class Solution {
    List<Integer> res = new LinkedList<>();

    public List<Integer> postorder(Node root) {
        traverse(root);
        return res;
    }

    public void traverse(Node root){
        if(root == null){
            return;
        }
        List<Node> children = root.children;
        for(Node node: children){
            traverse(node);
        }
        res.add(root.val);
    }
}

105. 从前序与中序遍历序列构造二叉树（20240220更新）

题目给出一个前序遍历的数组preorder和一个中序遍历的数组inorder，就二叉树。

我们知道前序遍历的第一个元素就是根节点，在中序遍历中，根节点左边的是左子树数据，右边的是有子树数据。

比如题目中给出preorder=[3,9,20,15,7], inorder = [9,3,15,20,7]，可以看出元素3所对应的节点就是二叉树的根节点。

在中序遍历中根节点左边的就是左子树数据，右边的就是右子树数据，所有[9]是左子树元素3的左子树序列，[15, 20, 7]是元素3的右子树序列。

以此类推，我们对左子树维护新的前序中序序列，构建出来左树，对右子树维护新的前序中序序列，构建出来右树。

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // init
        for(int i=0;i<inorder.length;i++){  // 为什么要用中序的数组，不可以用前序的？ 因为需要再从中序遍历里面分割出来左子树数据和右子树数据
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);

    }
    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
        if(preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int index = valToIndex.get(rootVal);

        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1);
        root.right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd);
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树（20240221更新）

我们昨天了一个一道类似的题目，根据前序和中序构造二叉树，当前题目也是类似的思路。构建一个build函数来动态的构建二叉树。

inorder=[9, 3, 15, 20, 7]

Postorder = [9, 15, 7, 20, 3]

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();  // 我们需要分割出来左子树和右子树的数据，这里定义个map，用来保存中序遍历元素的下标

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // inorder
        for(int i=0;i<inorder.length;i++){  // 为什么是中序遍历序列？后序可以吗？后序不行，因为我们要区分左右子树的序列，根据中序遍历，根节点左边是左子树数据，右边是右子树数据
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length-1,postorder, 0, postorder.length-1);
    }

    public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
        if(inStart>inEnd){
            return null;
        }
        int rootVal = postorder[postEnd];  // 
        int index = valToIndex.get(rootVal);
        int leftSize = index - inStart;  // 找到左子树的长度
        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, inStart, index-1, postorder, postStart, postStart+leftSize-1);  // 为啥-1?昨边size个,postStart下标是从0开始的postStart+leftSize-1就表示右边的下标
        root.right = build(inorder, index+1, inEnd,postorder, postStart+leftSize, postEnd-1);  // 为什么是postEnd-1？因为我们要去掉最后一个根节点数据
        return root;
    }
}

2583. 二叉树中的第 K 大层和（20240223更新）

好几天没没写题解了，但是力扣上面的每日一题我还是在做的，最近是关于树的，自己恰好有一点理解，正好能解，今天说的是二叉树中的第K大层和。

给你一棵二叉树的根节点和一个正整数k，树中的层和是指同一层上节点值的和。
返回树中第k大的层和(不一定不同)，如果树中少于k层，则返回-1。

简单来理解就是求二叉树的每层的和，看第k大的是和是多少。每层的和，这个我们能立马想到bfs，我们就把每层的节点val加起来，存到列表ans里面，最后返回ans的第ans.size()-k个元素。

这里需要注意，题目给出的返回值是long型，第二点就是最后题目说的小于k层的话，直接返回-1。

第三点就是排序后为什么ans.size()-k表示第几大元素？

比如ans = [1,2,3,4,5]，size = 5, k=2, 最后返回的最表示3， size=5， k=4的话，最后返回的是1。

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        // bfs 求解
        List<Long> ans = new LinkedList<>();
        if(root == null){
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int sz = q.size();
            long level = 0;
            for(int i=0;i<sz;i++){
                TreeNode node = q.poll();
                level += node.val;
                if(node.left!=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            ans.add(level);
        }   
        int n = ans.size();
        if(n<k){
            return -1;
        }
        // sort
        Collections.sort(ans);
        return ans.get(n-k); // 为什么n-k能表示最大第几个？
    }
}

这里补充一下java中数组、列表的排序实现，因为间隔了很久开始写java，有一些api不是很熟悉，在做题的过程中遇到就把他总结下来。

1、对数组进行排序，这里需要区分是原子类型还是包装类型，Arrays里面提供了一个sort的方法，可以用来排序，如果是原子类型的话，正序排序的话直接使用Arrays.sort(ans), 如果需要逆序排序的话，那么就只能进行转化了，1是将原子类型转成包装类型在排序，或者是正序排序了之后创建新的容器逆序遍历。如果是包装类型，可以在sort函数里面传入自定义的比较器来实现正序或者是逆序排序

2、对列表进行排序，这里也提供了一个Collections的util，里面也有一个sort的方法，也可以传入比较器来进行比较。一般列表都是有包装类型的泛型的。

List<Integer> res = new ArrayList<>();
Collections.sort(res, (a,b)->{
  return b-a;
});

2476. 二叉搜索树最近节点查询（20240224更新）

今天早上一大早起来做算法题，结果tle超时了。

这道题的题目可以跳转到链接里面看，大概得意思就是给出一个二叉搜索树，和一个正整数数组，其中ans[i] = [minx,max]，minx表示树中小于等于数组i的最大值，如果不存在就返回-1.

这个题做过一版就是先遍中序遍历树，这样子就得到了一个升序的数组，然后在遍历queries，找到其中最大最小值的下标，但是不出意外的超时了。然后看了题解，给出的题解里面使用到了二分查找回去对应元素的下标，其中还用到了ArraysList，我用的是LinkedList，这个也是导致超时的一个问题，后面需要去了解两者的差别。


class Solution {

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {

        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);

        List<List<Integer>> res = new ArrayList<>();
        for(int val: queries){
            int maxval = -1, minval = -1;
            int idx = binarySearch(ans, val);
            if(idx !=ans.size()){
                maxval = ans.get(idx);
                if(ans.get(idx) == val){
                    minval = val;
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(minval);
                    list.add(maxval);
                    res.add(list);
                    continue;
                }
            }
            if(idx>0){
                minval = ans.get(idx-1);
            }
            List<Integer> list2 = new ArrayList<>();
            list2.add(minval);
            list2.add(maxval);
            res.add(list2);
        }
        return res;
    }

    public void dfs(TreeNode root, List<Integer> ans){
        if(root == null){
            return;
        }
        dfs(root.left, ans);
        ans.add(root.val);
        dfs(root.right, ans);
    }
   public int binarySearch(List<Integer> arr, int target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}