✅🎡个人主页：程序猿追
✅🎡系列专栏：算法合集
✅🎡目前状态：创建Java学习之路（零基础到就业实战）系列，目前更新到JAVAWEB开发
✅🎡作者简介：大家好，我是程序猿追，全栈领域新星创作者，算法爱好者，常在作者周榜排名前30，某不知名的 ACMer
✅🎡推荐一款刷题面试找工作三不误的网站——牛客网
✅🎡个人名言：不积跬步无以至千里，趁年轻，使劲拼，给未来的自己一个交代！
目录
二叉树的前序遍历
题解代码
二叉树的中序遍历
题解代码
二叉树的后序遍历
题解代码
求二叉树的层序遍历
题解代码
二叉树的前序遍历
描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足 0≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同
示例1：
输入：
{1,#,2,3}返回值：
[1,2,3]
题解代码
import java.util.*;
public class Solution {
public void preorder(List<Integer> list, TreeNode root){
//遇到空节点则返回 fast-template
if(root == null)
return;
//先遍历根节点
list.add(root.val);
//再去左子树
preorder(list, root.left);
//最后去右子树
preorder(list, root.right);
}
public int[] preorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
//递归前序遍历
preorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;}
}二叉树的中序遍历
描述
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足 0≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：
{1,2,#,#,3}返回值：
[2,3,1]说明：
示例2
输入：
{}
返回值：
[]
示例3
输入：
{1,2}
返回值：
[2,1]
说明：
示例4
输入：
{1,#,2}
返回值：
[1,2]
题解代码
import java.util.*;
public class Solution {
public void inorder(List<Integer> list, TreeNode root){
//遇到空节点则返回 fast-template
if(root == null)
return;
//先去左子树
inorder(list, root.left);
//再访问根节点
list.add(root.val);
//最后去右子树
inorder(list, root.right);
}
public int[] inorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
//递归中序遍历
inorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;}
}二叉树的后序遍历
描述
给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围：二叉树的节点数量满足0≤n≤100 ，二叉树节点的值满足 11≤val≤100 ，树的各节点的值各不相同
样例图
示例1
输入：
{1,#,2,3}返回值：
[3,2,1]说明：
如题面图示例2
输入：
{1}返回值：
[1]
题解代码
import java.util.*;
public class Solution {
public void postorder(List<Integer> list, TreeNode root){
//遇到空节点则返回 fast-template
if(root == null)
return;
//先去左子树
postorder(list, root.left);
//再去右子树
postorder(list, root.right);
//最后访问根节点
list.add(root.val);
}
public int[] postorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
//递归后序遍历
postorder(list, root);
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;}
}求二叉树的层序遍历
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]]
数据范围：二叉树的节点数满足 1≤n≤105
示例1
输入：
{1,2}
返回值：
[[1],[2]]示例2
输入：
{1,2,3,4,#,#,5}
返回值：
[[1],[2,3],[4,5]]
题解代码
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer> > res = new ArrayList();
if(root == null)
//如果是空，则直接返回空数组 fast-template
return res;
//队列存储，进行层次遍历
Queue<TreeNode> q = new ArrayDeque<TreeNode>();
q.add(root);
while(!q.isEmpty()){
//记录二叉树的某一行
ArrayList<Integer> row = new ArrayList();
int n = q.size();
//因先进入的是根节点，故每层结点多少，队列大小就是多少
for(int i = 0; i < n; i++){
TreeNode cur = q.poll();
row.add(cur.val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
//每一层加入输出
res.add(row);
}
return res;}
}算法对程序员来说及其重要，语言和开发平台不断变化，但是万变不离其宗的是那些算法和理论，依稀记得我那个玩的很好的一个学长（在大二就拿到了 offer），他告诉我想找一个好的工作，那刷题一定是必不可少的文章来源：https://www.toymoban.com/news/detail-410610.html
现在算法刷题平台还是蛮多的，给大家介绍一个我认为与大厂关联最深的平台——牛客网文章来源地址https://www.toymoban.com/news/detail-410610.html
到了这里，关于【算法合集】学习算法第三天（二叉树遍历篇）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
