对于下图所示的二叉树
其先序、中序、后序遍历的序列如下：
- 先序遍历： A、B、D、F、G、C、E、H
- 中序遍历： B、F、D、G、A、C、E、H
- 后序遍历： F、G、D、B、H、E、C、A
- 层序遍历： A、B、C、D、E、F、G、H
/** * 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; * } * } */前序遍历
先序遍历操作过程：
若二叉树为空，则空操作，否则依次执行如下3个操作
- 访问根结点；
- 按先序遍历左子树；
- 按先序遍历右子树。
递归法
class Solution { public List preorderTraversal(TreeNode root) { List list = new ArrayList(); preorder(root, list); return list; } public void preorder(TreeNode root, List list){ if (root == null) return; list.add(root.val); preorder(root.left, list); preorder(root.right, list); }}迭代法
class Solution { public List preorderTraversal(TreeNode root) { List list = new ArrayList(); Stack stack = new Stack(); if (root != null) stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.peek(); list.add(stack.pop().val); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return list; }}中序遍历
中序遍历操作过程：
若二叉树为空，则空操作，否则依次执行如下3个操作
- 按中序遍历左子树；
- 访问根结点；
- 按中序遍历右子树。
递归法
class Solution { public List inorderTraversal(TreeNode root) { List list = new ArrayList(); inorder(root, list); return list; } public void inorder(TreeNode root, List list){ if (root == null) return; inorder(root.left, list); list.add(root.val); inorder(root.right, list); }}迭代法
class Solution { public List inorderTraversal(TreeNode root) { ArrayList list = new ArrayList(); Stack stack = new Stack(); TreeNode node = root; while (node != null || !stack.isEmpty()){ if (node != null){ stack.push(node); node = node.left; }else{ node = stack.peek(); list.add(stack.pop().val); node = node.right; } } return list; }}后序遍历
后序遍历操作过程：
若二叉树为空，则空操作，否则依次执行如下3个操作：
- 按后序遍历左子树；
- 按后序遍历右子树；
- 访问根结点。
递归法
class Solution { public List postorderTraversal(TreeNode root) { List list = new ArrayList(); postorder(root, list); return list; } public void postorder(TreeNode root, List list){ if (root == null) return; postorder(root.left, list); postorder(root.right, list); list.add(root.val); }}迭代法
class Solution { public List postorderTraversal(TreeNode root) { List list = new ArrayList(); Stack stack = new Stack(); TreeNode prev = null; // 记录上一个输出的结点 while (root != null || !stack.isEmpty()){ while (root != null) { // 从当前结点向“左下”遍历，找到位于“左下”方的结点 stack.push(root); root = root.left; }// 定位到没有左子树的结点，接着准备处理右边（要弹出是因为如果有右子树，是要先让右子树进栈的） root = stack.pop(); /*因为通过刚才的遍历知道不存在左子树了，现在开始向右走，下面的操作都是在没有左子树的前提下进行的*//*将当前结点值输出的条件是：【当前结点没有右子树】 或 【右子树的值已经输出过轮到当前结点了】*/ if (root.right == null || root.right == prev) { list.add(root.val); // 将当前结点的值输出 prev = root; // 用prev记录输出的结点 root = null; }else{ stack.push(root); root = root.right; } } return list; } }如果有左子树，就一直走下去；如果有右子树，则往右子树走一步，再一直往左走下去。
层序遍历
层序遍历，又称广度优先遍历。
class Solution { public List<List> levelOrder(TreeNode root) { List<List> list = new ArrayList(); ArrayDeque queue = new ArrayDeque(); if(root != null) queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); ArrayList tmp = new ArrayList(); for (int i = 0; i < size; i++){ TreeNode node = queue.poll(); tmp.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } list.add(tmp);// 若要返回其节点值自底向上的层序遍历，只需反转得到的list即可// Collections.reverse(list); } return list; }}