二叉树前中后序遍历的迭代版本

前序

public static void preOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } 二叉树的前序遍历 给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3] 1 2 / 3

输出: [1,2,3]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if(root==null) return ans; stack.push(root); while(!stack.isEmpty()){ TreeNode tmp = stack.pop(); ans.add(tmp.val); if(tmp.right!=null) stack.push(tmp.right); if(tmp.left!=null) stack.push(tmp.left); } return ans; } }

中序遍历

public static void inOrderIteration(TreeNode head) { if (head == null) { return; } TreeNode cur = head; Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || cur != null) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { cur = node.right; } } }

后序遍历

public static void postOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(head); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().value + " "); } } 二叉树的后序遍历 给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3] 1 2 / 3

输出: [3,2,1]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> st1 = new Stack<>(); Stack<Integer> st2 = new Stack<>(); if(root==null) return ans; st1.push(root); while(!st1.isEmpty()){ TreeNode tmp = st1.pop(); st2.push(tmp.val); if(tmp.left!=null) st1.push(tmp.left); if(tmp.right!=null) st1.push(tmp.right); } while(!st2.isEmpty()) ans.add(st2.pop()); return ans; } }