java二叉树前中后序遍历

本文主要是介绍java二叉树前中后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 代码随想录解题思路
• 力扣前序
• 力扣中序
• 力扣后序

递归遍历

// 前序遍历
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);}
}

迭代遍历

package origin;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) {// 定义resList<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_listif (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二叉树前中后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---