- 代码随想录解题思路
- 🆒力扣前序题目
- 🆒力扣中序题目
- 🆒力扣后序题目
递归遍历
// 前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preorder(root,res);
return res;
}
public void preorder(TreeNode root, List<Integer> res){
if(root==null) return ;
res.add(root.val);
preorder(root.left,res);
preorder(root.right,res);
}
}
// 中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
inorder(root,res);
return res;
}
public void inorder(TreeNode root,List<Integer> res){
if(root==null) return ;
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
}
// 后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null)
return;
postorder(root.left,res);
postorder(root.right,res);
res.add(root.val);
}
}
🆘二叉树的统一迭代遍历
💡一个大模板，前中后序只需要改变几句代码的顺序即可文章来源：https://www.toymoban.com/news/detail-848411.html
代码随想录思路文章来源地址https://www.toymoban.com/news/detail-848411.html
package com.tree;
import jdk.nashorn.internal.ir.SplitReturn;
import java.util.*;
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 demo12_BinaryTreeTraversal {
/**
* 二叉树的非递归前序遍历
*
* @param root
* @return 前序遍历的节点列表
*/
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) {
return res;
} else st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop();
if (node.right != null) st.push(node.right);
if (node.left != null) st.push(node.left);
st.push(node);
st.push(null);
} else {
st.pop();
node = st.pop();
res.add(node.val);
}
}
return res;
}
/**
* 二叉树的非递归中序遍历
*
* @param root
* @return 中序遍历的节点列表
*/
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) {
return res;
} else st.push(root);
while (!st.empty()) {
TreeNode cur = st.peek();
if (cur != null) {
st.pop();
//中序遍历：左根右，so入栈顺序是右根左，在根入栈之后记得入栈一个null节点标记
if (cur.right != null) st.push(cur.right);
st.push(cur);
st.push(null);
if (cur.left != null) st.push(cur.left);
} else {
st.pop();
cur = st.pop();
res.add(cur.val);
}
}
return res;
}
/**
* 二叉树的非递归后序遍历
*
* @param root
* @return 后序遍历的节点列表
*/
public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.empty()) {
TreeNode point = st.peek();
if (point != null) {
//出栈左右根，入栈根右左
st.pop();
st.push(point);
st.push(null);
if (point.right != null) st.push(point.right);
if (point.left != null) st.push(point.left);
} else {
st.pop();
point = st.pop();
res.add(point.val);
}
}
return res;
}
public static void main(String[] args) {
// 创建二叉树 [1,null,2,3]
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
System.out.println(preorderTraversal(root));
System.out.println(postorderTraversal(root));
System.out.println(inorderTraversal(root));
}
}
迭代遍历
import jdk.nashorn.internal.ir.SplitReturn;
import java.util.*;
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 demo12_BinaryTreeTraversal {
/**
* 二叉树的非递归中序遍历
*
* @param root
* @return 中序遍历的节点列表
*/
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root; // 设定一个指针
while (cur != null || !st.isEmpty()) {
if (cur != null) {
st.push(cur);
cur = cur.left;
} else {
cur = st.pop(); // 出栈
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
/**
* 二叉树的非递归前序遍历
*
* @param root
* @return 前序遍历的节点列表
*/
public static List<Integer> preorderTraversal(TreeNode root) {
// 定义res
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 定义栈
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode tmp = st.pop(); // 出栈
res.add(tmp.val);
if (tmp.right != null) {
st.push(tmp.right); // 先在栈中加入右节点，再加入左节点
}
if (tmp.left != null) {
st.push(tmp.left); // 因为左节点要先出栈，栈是FILO的结构
}
}
return res;
}
/**
* 二叉树的非递归后序遍历
*
* @param root
* @return 后序遍历的节点列表
*/
public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
res.add(node.val);
// 注意：入栈顺序相对于前序遍历有改变
// 前序遍历的入栈顺序是：中右左
// 后序遍历的顺序变成了：中左右，然后反转result_list
if (node.left != null) {
st.push(node.left);
}
if (node.right != null) {
st.add(node.right);
}
}
Collections.reverse(res);
return res;
}
public static void main(String[] args) {
// 创建二叉树 [1,null,2,3]
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
System.out.println(preorderTraversal(root));
System.out.println(postorderTraversal(root));
System.out.println(inorderTraversal(root));
}
}
到了这里，关于java二叉树前中后序遍历的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
