其先序、中序、后序遍历的序列如下：
- 先序遍历： 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<Integer> preorderTraversal(TreeNode root) { | |
| List<Integer> list = new ArrayList<Integer>(); | |
| preorder(root, list); | |
| return list; | |
| } | |
| public void preorder(TreeNode root, List<Integer> list){ | |
| if (root == null) return; | |
| list.add(root.val); | |
| preorder(root.left, list); | |
| preorder(root.right, list); | |
| } | |
| } |
迭代法
| class Solution { | |
| public List<Integer> preorderTraversal(TreeNode root) { | |
| List<Integer> list = new ArrayList<>(); | |
| Stack<TreeNode> 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<Integer> inorderTraversal(TreeNode root) { | |
| List<Integer> list = new ArrayList<Integer>(); | |
| inorder(root, list); | |
| return list; | |
| } | |
| public void inorder(TreeNode root, List<Integer> list){ | |
| if (root == null) return; | |
| inorder(root.left, list); | |
| list.add(root.val); | |
| inorder(root.right, list); | |
| } | |
| } |
迭代法
| class Solution { | |
| public List<Integer> inorderTraversal(TreeNode root) { | |
| ArrayList<Integer> list = new ArrayList<>(); | |
| Stack<TreeNode> 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<Integer> postorderTraversal(TreeNode root) { | |
| List<Integer> list = new ArrayList<Integer>(); | |
| postorder(root, list); | |
| return list; | |
| } | |
| public void postorder(TreeNode root, List<Integer> list){ | |
| if (root == null) return; | |
| postorder(root.left, list); | |
| postorder(root.right, list); | |
| list.add(root.val); | |
| } | |
| } |
迭代法
| class Solution { | |
| public List<Integer> postorderTraversal(TreeNode root) { | |
| List<Integer> list = new ArrayList<>(); | |
| Stack<TreeNode> 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<Integer>> levelOrder(TreeNode root) { | |
| List<List<Integer>> list = new ArrayList<>(); | |
| ArrayDeque<TreeNode> queue = new ArrayDeque<>(); | |
| if(root != null) queue.offer(root); | |
| while (!queue.isEmpty()){ | |
| int size = queue.size(); | |
| ArrayList<Integer> 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; | |
| } | |
| } |
