作者：渴望力量的土狗
博客主页：渴望力量的土狗的博客主页
专栏：手把手带你刷牛客
工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
点击免费注册和我一起刷题吧
目录
二叉树的前序遍历：
一、解题思路：递归
二、解题思路：迭代
二叉树的中序遍历 ：
一、解题思路：递归
二、解题思路：迭代
二叉树的后序遍历 ：
一、解题思路：递归
二、解题思路：迭代
二叉树的前序遍历的记忆法则是“根左右"，即先遍历根节点，再遍历左子树节点，再遍历右子树节点。
如图所示：
其遍历结果为【A, B, D, E, C, F, G】
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足1≤n≤100 ，二叉树节点的值满足1≤val≤100，树的各节点的值各不相同
示例 1：
输入：
{1,#,2,3}
返回值：
[1,2,3]public class Solution {
List<Integer> list = new ArrayList<>();
public int[] preorderTraversal (TreeNode root) {
List<Integer> list = preOrder(root);
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
List<Integer> preOrder(TreeNode node) {
if (node == null) {
return list;
}
list.add(node.val);
preOrder(node.left);
preOrder(node.right);
return list;
}
}import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
public int[] preorderTraversal (TreeNode root) {
// 结果集合
ArrayList<Integer> arr = new ArrayList();
if(root == null) {
return new int[0];
}
TreeNode current;
// LinkedList 当作栈来使用
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.addFirst(root);
while(!list.isEmpty()) {
current = list.removeFirst();
arr.add(current.val);
if(current.right != null) {
list.addFirst(current.right);
}
if(current.left != null) {
list.addFirst(current.left);
}
}
// 循环赋值。
int[] res = new int[arr.size()];
for(int i = 0; i < arr.size(); i++) {
res[i] = arr.get(i);
}
return res;
}
}
中序遍历是 二叉树遍历 的一种，也叫做 中根遍历 、中序周游。 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足10000≤n≤1000，树上每个节点的值满足 −1000≤val≤1000
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1：
输入：
{1,2,#,#,3}
返回值：
[2,3,1]import java.util.*;
public class Solution {
public void inorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
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;
}
}
import java.util.*;
public class Solution {
public int[] inorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
Stack<TreeNode> s = new Stack<TreeNode>();
//空树返回空数组
if(root == null)
return new int[0];
//当树节点不为空或栈中有节点时
while(root != null || !s.isEmpty()){
//每次找到最左节点
while(root != null){
s.push(root);
root = root.left;
}
//访问该节点
TreeNode node = s.pop();
list.add(node.val);
//进入右节点
root = node.right;
}
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
}
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点
给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围：二叉树的节点数量满足 1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同
输入：
{1,#,2,3}
返回值：
[3,2,1]
import java.util.*;
public class Solution {
public void postorder(List<Integer> list, TreeNode root){
//遇到空节点则返回
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;
}
}
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode pre = null;
while(root != null || !s.isEmpty()){
//每次先找到最左边的节点
while(root != null){
s.push(root);
root = root.left;
}
//弹出栈顶
TreeNode node = s.pop();
//如果该元素的右边没有或是已经访问过
if(node.right == null || node.right == pre){
//访问中间的节点
list.add(node.val);
//且记录为访问过了
pre = node;
}else{
//该节点入栈
s.push(node);
//先访问右边
root = node.right;
}
}
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
}
“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！