二叉树的中序遍历（二叉树前中后序遍历）

来源：力扣（LeetCode）前序遍历链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

中序遍历链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

后序遍历链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

题目描述

二叉树的前序遍历节点访问顺序：根节点、左节点、右节点二叉树的中序遍历节点访问顺序：左节点、根节点、右节点二叉树的后序遍历节点访问顺序：左节点、右节点、根节点

题目分析

二叉树前中后序遍历主要提供了两种方法：

前序遍历代码实现

public class PreOrder { public static void main(String[] args) { PreOrder preOrder = new PreOrder(); // TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); TreeNode root = null; preOrder.preorderTraversal(root); preOrder.preorder2(root); } /** * 迭代算法 * * @param root * @return */ public List<Integer> preorder2(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null){ return list; } LinkedList<TreeNode> stack = new LinkedList(); stack.add(root); while (!stack.isEmpty()) { TreeNode treeNode = stack.getLast(); list.add(treeNode.val); stack.removeLast(); if (treeNode.right != null) { stack.add(treeNode.right); } if (treeNode.left != null) { stack.add(treeNode.left); } } System.out.println(list); return list; } /** * 递归 * * @param root * @return */ public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); order(root, list); System.out.println(list); return list; } private void order(TreeNode root, List<Integer> list) { if (root == null) { return; } list.add(root.val); if (root.left != null) { order(root.left, list); } if (root.right != null) { order(root.right, list); } } }

中序遍历代码实现

public class MiddleOrder { public static void main(String[] args) { MiddleOrder preOrder = new MiddleOrder(); TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); // TreeNode root = null; preOrder.preorderTraversal(root); preOrder.preorder2(root); } /** * 迭代算法 * * @param root * @return */ public List<Integer> preorder2(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if (root == null) { return list; } LinkedList<TreeNode> stack = new LinkedList(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.addLast(root); root = root.left; } root = stack.removeLast(); list.add(root.val); root = root.right; } System.out.println(list); return list; } /** * 递归 * * @param root * @return */ public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); order(root, list); System.out.println(list); return list; } private void order(TreeNode root, List<Integer> list) { if (root == null) { return; } if (root.left != null) { order(root.left, list); } list.add(root.val); if (root.right != null) { order(root.right, list); } } }

后序遍历代码实现

public class AfterOrder { public static void main(String[] args) { AfterOrder preOrder = new AfterOrder(); TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); // TreeNode root = null; preOrder.preorderTraversal(root); preOrder.preorder2(root); } /** * 迭代算法 * * @param root * @return */ public List<Integer> preorder2(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if (root == null) { return list; } LinkedList<TreeNode> stack = new LinkedList(); TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.addLast(root); root = root.left; } root = stack.removeLast(); if(root.right == null || root.right == prev){ // 根节点 list.add(root.val); prev = root; root = null; } else { stack.addLast(root); root = root.right; } } System.out.println(list); return list; } /** * 递归 * * @param root * @return */ public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); order(root, list); System.out.println(list); return list; } private void order(TreeNode root, List<Integer> list) { if (root == null) { return; } if (root.left != null) { order(root.left, list); } if (root.right != null) { order(root.right, list); } list.add(root.val); } }

二叉树前中后序遍历，两种方法的复杂度

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！