当前位置： 首页 > news >正文

代码随想录算法训练营第十一天

news 2025/4/8 8:53:13

LeetCode/卡码网题目:

  • 144. 二叉树的前序遍历
  • 94. 二叉树的中序遍历
  • 145. 二叉树的后序遍历
  • 102. 二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199. 二叉树的右视图
  • 637. 二叉树的层平均值
  • 429. N 叉树的层序遍历
  • 515. 在每个树行中找最大值
  • 116. 填充每个节点的下一个右侧节点指针
  • 117. 填充每个节点的下一个右侧节点指针 II
  • 104. 二叉树的最大深度
  • 111. 二叉树的最小深度

其他:

今日总结
往期打卡

144. 二叉树的前序遍历

跳转:144. 二叉树的前序遍历

问题:

在这里插入图片描述

思路:

递归,迭代,空指针标记模拟递归

代码(递归):

void handle(TreeNode root,List<Integer> list){if(root == null) return;list.add(root.val);handle(root.left,list); handle(root.right,list);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();handle(root,ans);return ans;}

代码(迭代):

class Solution {public List<Integer> preorderTraversal(TreeNode root) {if(root==null) return new ArrayList<>();Stack<TreeNode> stack = new Stack<>();stack.push(root);List<Integer> ans = new ArrayList<>();while(!stack.isEmpty()){TreeNode tmp = stack.pop();ans.add(tmp.val);if(tmp.right!=null){stack.push(tmp.right);}if(tmp.left!=null){stack.push(tmp.left);} }return ans;}
}

代码(空指针标记模拟递归):

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root==null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();if(tmp==null){tmp = stack.pop();ans.add(tmp.val);}else{if(tmp.right!=null) stack.add(tmp.right);if(tmp.left!=null) stack.add(tmp.left);stack.add(tmp);stack.add(null);}}return ans;}

94. 二叉树的中序遍历

跳转: 94. 二叉树的中序遍历

在这里插入图片描述

问题:

思路:

递归,迭代,空指针标记模拟递归

代码(递归):

void handle(TreeNode root,List<Integer> list){if(root == null) return;handle(root.left,list);list.add(root.val);handle(root.right,list);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();handle(root,ans);return ans;}

代码(迭代):

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root==null) return ans;Stack<TreeNode> stack = new Stack<>();while(root!=null||!stack.isEmpty()){if(root!=null){stack.push(root);root = root.left;}else{root = stack.pop();ans.add(root.val);root = root.right;}}return ans;}
}

代码(空指针标记模拟递归):

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root==null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();if(tmp==null){tmp = stack.pop();ans.add(tmp.val);}else{if(tmp.right!=null) stack.add(tmp.right);stack.add(tmp);stack.add(null);if(tmp.left!=null) stack.add(tmp.left);}}return ans;}

145. 二叉树的后序遍历

跳转: 145. 二叉树的后序遍历

问题:

在这里插入图片描述

思路:

递归,迭代,空指针标记模拟递归

代码(递归):

void handle(TreeNode root,List<Integer> list){if(root == null) return;handle(root.left,list);handle(root.right,list);list.add(root.val);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();handle(root,ans);return ans;}

代码(迭代):

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null)return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();ans.add(tmp.val);if(tmp.left!=null) stack.add(tmp.left);if(tmp.right!=null) stack.add(tmp.right);}Collections.reverse(ans);return ans;}

代码(空指针标记模拟递归):

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null)return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();if(tmp==null){tmp = stack.pop();ans.add(tmp.val);}else{stack.push(tmp);stack.push(null);if(tmp.right!=null) stack.push(tmp.right);if(tmp.left!=null) stack.push(tmp.left);}}return ans;}

102. 二叉树的层序遍历

跳转: 102. 二叉树的层序遍历

问题

在这里插入图片描述

思路:

利用队列层序遍历

代码:

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if(root==null) return ans;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){List<Integer> list = new ArrayList<>();int len = queue.size();while(len-->0){TreeNode tmp = queue.poll();list.add(tmp.val);if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}ans.add(list);}return ans;}
}

107.二叉树的层次遍历II

跳转: 107. 二叉树的层序遍历 II

问题

在这里插入图片描述

代码:

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if(root==null) return ans;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){List<Integer> list = new ArrayList<>();int len = queue.size();while(len-->0){TreeNode tmp = queue.poll();list.add(tmp.val);if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}ans.add(list);}Collections.reverse(ans);return ans;}
}

199. 二叉树的右视图

跳转: 199. 二叉树的右视图

问题

在这里插入图片描述

代码:

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

637. 二叉树的层平均值

跳转: 637. 二叉树的层平均值

问题

在这里插入图片描述

代码:

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> ans = new ArrayList<>();if(root==null) return ans;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){Double avg=0.0;int len = queue.size();for(int i=0;i<len;i++){TreeNode tmp = queue.poll();avg += tmp.val;if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}if(len!=0)ans.add(avg/len);}return ans;}
}

429. N 叉树的层序遍历

跳转: 429. N 叉树的层序遍历

问题

在这里插入图片描述

代码:

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ans = new ArrayList<>();if(root==null) return ans;Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){List<Integer> list = new ArrayList<>();int len = queue.size();while(len-->0){Node tmp = queue.poll();list.add(tmp.val);for(Node child:tmp.children){queue.add(child);}}ans.add(list);}return ans;}
}

515. 在每个树行中找最大值

跳转: 515. 在每个树行中找最大值

问题

在这里插入图片描述

代码:

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root==null) return ans;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int max=Integer.MIN_VALUE;int len = queue.size();for(int i=0;i<len;i++){TreeNode tmp = queue.poll();max = Math.max(max,tmp.val);if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}if(len>0)ans.add(max);}return ans;}
}

116. 填充每个节点的下一个右侧节点指针

跳转: 116. 填充每个节点的下一个右侧节点指针

问题

在这里插入图片描述

代码:

class Solution {public Node connect(Node root) {if(root==null) return null;Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int len = queue.size();for(int i=0;i<len;i++){Node tmp = queue.poll();if(i==len-1) tmp.next = null;else tmp.next = queue.peek();if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}}return root;}
}

117. 填充每个节点的下一个右侧节点指针 II

跳转: 117. 填充每个节点的下一个右侧节点指针 II

问题

在这里插入图片描述

代码:

class Solution {public Node connect(Node root) {if(root==null) return null;Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int len = queue.size();for(int i=0;i<len;i++){Node tmp = queue.poll();if(i==len-1) tmp.next = null;else tmp.next = queue.peek();if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}}return root;}
}

104. 二叉树的最大深度

跳转: 104. 二叉树的最大深度

问题

在这里插入图片描述

代码:

class Solution {public int maxDepth(TreeNode root) {if(root==null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int deep = 0;while(!queue.isEmpty()){int len = queue.size();deep ++;for(int i=0;i<len;i++){TreeNode tmp = queue.poll();if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);}}return deep;}
}

111. 二叉树的最小深度

跳转: 111. 二叉树的最小深度

问题

在这里插入图片描述

代码:

class Solution {public int minDepth(TreeNode root) {if(root==null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int deep = 0;while(!queue.isEmpty()){int len = queue.size();deep ++;for(int i=0;i<len;i++){TreeNode tmp = queue.poll();if(tmp.left!=null) queue.add(tmp.left);if(tmp.right!=null) queue.add(tmp.right);if(tmp.left==null&&tmp.right==null) return deep;}}return deep;}
}

总结

练习了递归遍历和层序遍历,后面都是层序遍历的题,所以每题改动不大
为什么如此匆忙,因为电脑快没电了
建议去力扣自己练习,使用效果更佳

往期打卡

代码随想录算法训练营第一天

代码随想录算法训练营第二天

代码随想录算法训练营第三天

代码随想录算法训练营第四天

代码随想录算法训练营周末一

代码随想录算法训练营第五天

代码随想录算法训练营第六天

代码随想录算法训练营第七天

代码随想录算法训练营第八天

代码随想录算法训练营第九天

代码随想录算法训练营第十天

代码随想录算法训练营周末二


http://www.mrgr.cn/news/97478.html

相关文章：

  • 2025-04-07 NO.3 Quest3 MR 配置
  • 《从零搭建Vue3项目实战》（AI辅助搭建Vue3+ElemntPlus后台管理项目）零基础入门系列第二篇:项目创建和初始化
  • RAG中构建个人知识库
  • Python高级爬虫之JS逆向+安卓逆向1.2节: 变量与对象
  • 从传递函数到PID控制器
  • C++20 统一容器擦除：std::erase 和 std::erase_if
  • nacos集群启动问题
  • 2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡
  • 【Vue】选项卡案例——NBA新闻
  • Linux学习笔记（1） 目录结构与路径描述：对比 Windows 系统差异（期末，期中复习笔记全）
  • 前缀和和差分笔记
  • 【JS】二分查找
  • 【Pandas】pandas DataFrame astype
  • 4月7日随笔
  • 内网文件传输新体验，聊天、传输、自定义，一应俱全
  • C++中常用的十大排序方法之4——希尔排序
  • Redlinux（2025.3.29）
  • rhcsa第三次作业
  • 手搓多模态-06 数据预处理
  • 操作系统概述（3）