二叉树的非递归遍历（背诵版、Java）二叉树的非递归遍历（背诵版

在程序员的技术面试中，对二叉树的非递归遍历是一个高频考点。本篇文章以备战面试为目的，提供简单易懂、方便记忆的算法模板。

1、背景介绍 1.1、二叉树的定义 Java语言描述的二叉树的数据结构如下：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

1.2、二叉树的层次遍历在讲解树的前中后序遍历的非递归版之前，首先介绍一下大家非常熟悉的二叉树的层次遍历。

题目描述：给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
题目来源：leetcode 102题

解法
可以通过队列来实现二叉树的层次遍历。在Java中队列通过接口Queue定义，LinkedList是Queue的实现类。
当只需要按序输出不考虑层次的时候：

public void levelOrder(TreeNode root) { if (root == null) return; Queue queue = new LinkedList<>(); queue.add(root); //根节点入队while (!queue.isEmpty()) { TreeNode t = queue.poll(); //出队队首元素 System.out.println(t.val); if (t.left != null) queue.add(t.left); //先左孩子入队 if (t.right != null) queue.add(t.right); //再右孩子入队 } }

题目要求按层保存再二维列表中：

public List> levelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.add(root); //根节点入队while (!queue.isEmpty()) { int size = queue.size(); //记录当前层节点数量 ArrayList subList = new ArrayList<>(); //记录当前层节点数据 for (int i = 0; i < size; i++) { TreeNode t = queue.poll(); //出队队首元素 subList.add(t.val); if (t.left != null) queue.add(t.left); //先左孩子入队 if (t.right != null) queue.add(t.right); //再右孩子入队 } result.add(subList); }return result; }

2、前序遍历的非递归算法

题目描述：给定一个二叉树，返回它的前序遍历。
题目来源：leetcode 144题
在熟练层次遍历的基础上，记忆前序遍历的非递归算法显得十分简单。
记忆诀窍：队列换栈，左右颠倒。
队列换栈，就是将层次遍历使用到的队列换成栈，相应的入队出队操作也要换成入栈出栈操作。
左右颠倒，就是将层次遍历先左后右的入队操作，改成先右后左的入栈操作。

实现如下：

public void preorderTraversal(TreeNode root) { if (root == null) return; Stack s = new Stack<>(); s.push(root); //根节点入队while (!s.isEmpty()) { TreeNode t = s.pop(); //出栈栈顶元素 System.out.println(t.val); if (t.right != null) s.push(t.right); //先右孩子入栈 if (t.left != null) s.push(t.left); //再左孩子入栈} }

3、后序遍历的非递归算法

题目描述：给定一个二叉树，返回它的后序遍历。
题目来源：leetcode 145题
在熟练前序遍历的基础上，记忆后序遍历的非递归算法显得十分简单。
记忆诀窍：左右颠倒，结果逆置
前序遍历的顺序是：根 → 左 → 右
后序遍历的顺序是：左 → 右 → 根

将前序遍历转变成后序遍历的方式：
1、左右颠倒：将前序遍历左右孩子的顺序颠倒，则为：根 → 右 → 左。
2、结果逆置：再将整个遍历结果逆序，则为：左 → 右 → 根。
3、这时的遍历顺序已经和后序遍历的顺序一致

public void postorderTraversal(TreeNode root) { if (root == null) return; Stack s1 = new Stack<>(); Stack s2 = new Stack<>(); //通过栈将结果逆置 s1.push(root); while (!s1.isEmpty()) { TreeNode t = s1.pop(); s2.push(t); if (t.left != null) s1.push(t.left); if (t.right != null) s1.push(t.right); }while (!s2.isEmpty()) { System.out.println(s2.pop().val); } }

4、中序遍历的非递归算法

【二叉树的非递归遍历（背诵版、Java）】题目描述：给定一个二叉树，返回它的中序遍历。
题目来源：leetcode 94题

public void inorderTraversal_2(TreeNode root) { Stack s = new Stack<>(); TreeNode curr = root; //指针指向根while (curr != null || !s.isEmpty()) { while (curr != null) {//指针入栈并左移 s.push(curr); curr = curr.left; } TreeNode pop = s.pop(); System.out.println(pop.val); curr = pop.right; } }