算法：Java构建二叉树并迭代实现二叉树的前序、中序、后序遍历

二叉树并迭代实现二叉树的前序、中序、后序遍历"/>

算法：Java构建二叉树并迭代实现二叉树的前序、中序、后序遍历

先自定义一下二叉树的类：

// 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;}
}

 一个代码里面同时实现二叉树的前序、中序、后序遍历：

以该二叉树为例

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;class preorderTraversalSolution {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.right = new TreeNode(6);Solution sol = new Solution();// 前序、中序、后序System.out.println(sol.preorderTraversal(root).toString());  //[1, 2, 4, 5, 3, 6]System.out.println(sol.inorderTraversal(root).toString());  //[4, 2, 5, 1, 3, 6]System.out.println(sol.postorderTraversal(root).toString());  //[4, 5, 2, 6, 3, 1]}
}class Solution {//前序遍历public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while(!stack.isEmpty() || node != null){while (node != null) {res.add(node.val);  //相比中序遍历，只有这行代码换了位置stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return res;}//中序遍历public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while(!stack.isEmpty() || node != null){while (node != null) {stack.push(node);node = node.left;}node = stack.pop();res.add(node.val);  //相比前序遍历，只有这行代码换了位置node = node.right;}return res;}//后序遍历public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;TreeNode pre = null;while(!stack.isEmpty() || node != null){while (node != null) {stack.push(node);node = node.left;}node = stack.pop();if (node.right == null || node.right == pre) {//如果不存在右子树，则输出该节点的值//如果该节点的右结点刚刚遍历过了，则也应该输出该节点的值res.add(node.val);pre = node;node = null;}else{//如果存在右子树，则重新放回栈中，因为它的值要在右子树遍历完之后添加stack.push(node);node = node.right;}}return res;}
}

 三种遍历方式的Java递归实现在这里：算法：Java构建二叉树并递归实现二叉树的前序、中序、后序遍历-CSDN博客