如果N代表根节点,L代表根节点的左子树,R代表根节点的右子树,则根据遍历根节点的先后次序有以下遍历方式:
1. NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。(简记为:根左右)
2. LNR:中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。(简记为:左根右)
3. LRN:后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。(简记为:左右根)
!!!记住加粗的九个字
eg: 给出下面二叉树的三种遍历
前序遍历(根左右):A B D E H C F G
中序遍历(左根右):D B E H A F C G
后序遍历(左右根):D H E B F G C A
临时搭建一个二叉树,只是为了测试用例
class Node{public char val;public Node left;//左孩子--左子树public Node right;//右孩子--右子树public Node(char val){this.val = val;}}public class BinaryTree {public Node buildTree(){//临时搭建一个二叉树,只是为了测试Node A = new Node('A');Node B = new Node('B');Node C = new Node('C');Node D = new Node('D');Node E = new Node('E');Node F = new Node('F');Node G = new Node('G');Node H = new Node('H');A.left = B;A.right = C;B.left = D;B.right = E;E.right = H;C.left = F;C.right = G;return A;}// 前序遍历---根左右void preOrderTraversal(Node root){if (root == null){return;}System.out.print(root.val+" ");preOrderTraversal(root.left);preOrderTraversal(root.right);}// 中序遍历---左根右void inOrderTraversal(Node root){if (root == null){return;}inOrderTraversal(root.left);System.out.print(root.val+" ");inOrderTraversal(root.right);}// 后序遍历---左右根void postOrderTraversal(Node root){if (root == null){return;}postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val+" ");}}
递归 + 非递归实现:(附LeetCode链接)
1、:
144. 二叉树的前序遍历
https://leetcode-/problems/binary-tree-preorder-traversal/
给定一个二叉树,返回它的前序遍历。(根左右)
示例:
输入: [1,null,2,3] 1\2/3 输出: [1,2,3]
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> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}System.out.print(root.val+" ");list.add(root.val);List<Integer> left = preorderTraversal(root.left);//要考虑接收它的返回值list.addAll(left);//用list来接收List<Integer> right = preorderTraversal(root.right);list.addAll(right);return list;}}
2>非递归----用栈实现
class Solution {//非递归实现public List<Integer> preorderTraversal(TreeNode root) {List <Integer> list = new ArrayList<>();if(root == null){return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.empty()){while (cur != null){stack.push(cur);list.add(cur.val);cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}return list;}}
2、:
94. 二叉树的中序遍历(左根右)
https://leetcode-/problems/binary-tree-inorder-traversal/
给定一个二叉树,返回它的中序遍历。
示例:
输入: [1,null,2,3]1\2/3输出: [1,3,2]
1>递归
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}List<Integer> left = inorderTraversal(root.left);list.addAll(left);list.add(root.val);List<Integer> right = inorderTraversal(root.right);list.addAll(right);return list;}}
2>非递归
class Solution {//非递归public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.empty()){while(cur!= null){stack.push (cur);cur = cur.left;}TreeNode top = stack.pop();list.add(top.val);cur = top.right;}return list;}}
3、:
145. 二叉树的后序遍历(左右根)
https://leetcode-/problems/binary-tree-postorder-traversal/
给定一个二叉树,返回它的后序遍历。
示例:
输入: [1,null,2,3] 1\2/3 输出: [3,2,1]
1>递归
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}List<Integer> left = postorderTraversal(root.left);list.addAll(left);List<Integer> right = postorderTraversal(root.right);list.addAll(right);list.add(root.val);return list;}}
2>非递归
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = cur;while(cur != null || !stack.empty()){while(cur != null ){stack.push(cur);cur = cur.left;}cur = stack.peek();if(cur.right == null || cur.right == prev){list.add(cur.val);stack.pop();prev = cur;cur = null;}else{cur = cur.right;}}return list;}}
4、层序遍历
设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从
左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是
层序遍历。
102. 二叉树的层序遍历
https://leetcode-/problems/binary-tree-level-order-traversal/
给你一个二叉树,请你返回其按层序遍历得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7]
,
3/ \9 20/ \15 7
返回其层次遍历结果:
[[3],[9,20],[15,7]]
/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode(int x) { val = x; }* }*/class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new LinkedList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> list = new ArrayList<>();while (size > 0){TreeNode cur = queue.poll();if (cur != null){list.add(cur.val);if (cur.left != null){queue.offer(cur.left);}if (cur.right != null){queue.offer(cur.right);}}size--;}ret.add(list);}return ret;}}