每日一刷——二叉树——12.09

🕗 发布于 2024-12-11 09:04 数据结构 算法 leetcode java 面试

第一题：二叉树的层序遍历

题目描述：102. 二叉树的层序遍历 - 力扣（LeetCode）

我的思路：

拿到这个题目，我首先想到的是利用队列来模拟，给我二叉树的根节点，然后我来返回每一层的各个节点，但是为啥我甚至觉得这个题目给的输入就是按照层序遍历来给的呢？？

然后感觉还有一个点就是咋返回成几个list嵌套

===>二叉树题目就是培养递归思维的

题目分析：

由于先进先出，取出一个节点之后，就再往里边添加它自己的左右孩子，这样左右孩子的顺序还是在本层节点的后边，但是在下一层其他节点的前面

===》1.怎么返回成几个list嵌套？那就每一层安排一个list，这个完了之后就添加到答案数组中，

===》2.怎么知道这一层有多少个数字? 其实就是上一层执行了往队列里边添加数字了之后，它自己就走了，上一层的数字都走了之后，就可以发现此时，队列里边就是下一层即将要执行的数字，所以就定义一个count变量，将count=queue.size()

笑死，每次都感觉自己的思维能力不够，哎，还要多模仿多练习啊.....

知识点回顾：

1.List

在获得List对象之后，就可以对其进行元素的添加、删除、修改和查询等操作了。下面是一些常用的List元素操作方法：

===>添加元素:

向List集合中添加元素，我们可以使用add()方法、addAll()方法和ListIterator的add()方法。这些方法分别具有以下特点：

add()方法：将指定元素添加到List的末尾；
addAll()方法：将指定集合中的所有元素添加到List的末尾；
ListIterator的add()方法：将指定元素插入到ListIterator当前位置。

2.queue

当使用LinkedList时：

import java.util.LinkedList;
import java.util.Queue;

public class LinkedListExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 向队列添加元素
        queue.add(1);
        queue.add(2);

        // 使用poll和peek方法
        System.out.println(queue.poll()); // 输出: 1
        System.out.println(queue.peek());  // 输出: 2
    }
}

1.E poll(): 移除并返回队列头部的元素，如果没有元素则返回null。

2.E peek(): 返回队列头部的元素但不移除它，如果没有元素则返回null。

题解：

/**
 * 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>> levelOrder(TreeNode root) {
        List<List<Integer>> ans =new ArrayList<>();
        Queue<TreeNode> queue =new LinkedList<>();
        queue.add(root);
        if(root == null)
            return ans;
        else{    //可是这个应该是需要记录每一行究竟有多少个吧
            while(!queue.isEmpty()){
                int count =queue.size();
                //要用两个数组
                List<Integer> list =new ArrayList<>();
                while(count >0){
                    TreeNode temp =queue.poll();
                    list.add(temp.val);
                    if(temp.left!=null)
                        queue.add(temp.left);
                    if(temp.right!=null){
                        queue.add(temp.right);
                    }
                    count--;
                }
                ans.add(list);
            }
            return ans;
        }
    }
}

第二题：二叉树的最大深度

题目描述：104. 二叉树的最大深度 - 力扣（LeetCode）

我的思路：

感觉是深度优先遍历，用一个栈？

好吧，感觉根本不需要用到栈，因为用栈是可以储存节点，这样便于我们把节点打印出来，现在我们并不需要打印，所以也就没什么必要用到栈，好吧。

呜呜呜

题目分析：

这个题目的思路就是：

用一个外部的变量来定义每一条路上的深度，然后求一下最大值，

知识点回顾：

1.stack的常见用法：

我的题解：

/**
 * 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 int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        //这里是往下边递归，然后发现有没有最大值
        else{
            return traverse(root);
        }
    }

    public static int depth=0;
    //往下遍历
    public static int traverse(TreeNode node){
        depth++;
        while(node!=null){
            traverse(node.left);
            traverse(node.right);
        }
    }
}

改进上一次的代码：

1.要用一个depth求每一条路的最大深度，

还要用一个res记录目前的最大深度

2.那么res什么时候使用，就是当判断到自己什么时候是空了，自己空了，就更新这个值

3.然后就是在递归遍历左边和右边中间或者两旁的一些代码，就是用来思考这个节点的前序时应该做什么操作，后序做什么操作，中序做什么操作

4.这里又忘记返回了，这里为啥要返回呢？因为到达了末端了，下边的代码只有往下走的功能，到达尽头了还不回头，就要时间超出限制了。

 if(node==null){
            res=Math.max(res,depth);
            return;

时间超时了哈，栓Q

/**
 * 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 int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        //这里是往下边递归，然后发现有没有最大值
        else{
            traverse(root);
            return res;
        }
    }

    public static int depth=0;
    public static int res=0;   //存放每一条路上的最大值
    //往下遍历
    public static void traverse(TreeNode node){
        if(node==null){
            res=Math.max(res,depth);
            return;   //这里又忘记返回了，这里为啥要返回呢？  因为到达了末端了，下边的代码只有往下走的功能，到达尽头了还不回头，就要时间超出限制了
        }
        while(node!=null){
            depth++;
            traverse(node.left);
            traverse(node.right);
            depth--;
            //把它想象成一个指针
        }
    }
}

感觉自己的思路很乱，就是不知道从何开始想这个题目，然后很多思路糅合在一起，像一团乱码

正确题解：

没事，我们还有一种思路哈，惹惹

/**
 * 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 int maxDepth(TreeNode root) {
       if(root ==null)
            return 0;
        int leftMax =maxDepth(root.left);
        int rightMax =maxDepth(root.right);
        int res =Math.max(leftMax,rightMax) +1;

        return res;
    }
}

往下不断递归，上一层应该是下边两层里边的最大值的深度+1，也就是说这个int的位置放在，左右都求完深度之后，又回到了自己这里，然后深度+1

第三题：二叉树的锯齿形层序遍历

题目描述：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目分析：

其实和第一题很类似，但是要用双端队列写，然后添加一个flag，用于控制此时的方向

题解：

/**
 * 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>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans =new ArrayList<>();
        if(root==null){
            return ans;
        }
        LinkedList<TreeNode> deque =new LinkedList<>();  //双端队列
        deque.add(root); //先把头节点放进去
        int size=0;
        boolean isHead =true ;//用来控制锯齿的顺序
        while(!deque.isEmpty()){
            size =deque.size();//先得到size
            List<Integer> curLevel = new ArrayList<>();
            for(int i =0;i<size;i++){  //搞size次
                TreeNode cur =isHead ? deque.pollFirst() :deque.pollLast();
                curLevel.add(cur.val);
                if(isHead){
                    if(cur.left !=null){
                        deque.addLast(cur.left);
                    }
                    if(cur.right!=null){
                        deque.addLast(cur.right);
                    }
                }else{
                    if(cur.right!=null){
                        deque.addFirst(cur.right);
                    }
                    if(cur.left !=null){
                        deque.addFirst(cur.left);
                    }
                }
            }
            ans.add(curLevel);
            isHead =!isHead;

        }
        return ans;
    }
}

没办法，多练习吧

原文地址：https://blog.csdn.net/2301_80073593/article/details/144359928

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：WebRTC 的核心：RTCPeerConnection
下一篇：python面向对象编程：访问限制

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

每日一刷——二叉树——12.09

第一题：二叉树的层序遍历

题目描述：102. 二叉树的层序遍历 - 力扣（LeetCode）

我的思路：

题目分析：

知识点回顾：

1.List

2.queue

题解：

第二题：二叉树的最大深度

题目描述：104. 二叉树的最大深度 - 力扣（LeetCode）

我的思路：

题目分析：

知识点回顾：

1.stack的常见用法：

我的题解：

改进上一次的代码：

时间超时了哈，栓Q

正确题解：

第三题：二叉树的锯齿形层序遍历

题目描述：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目分析：

题解：

相关文章