1. 二叉树的前序遍历（深度优先遍历）
二叉树的节点定义
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}
递归实现：
public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int fisrtTraversal(TreeNode node) {// 判断该节点是否存在if (node == null) {return 0;}list.add(node.val);firstTraversal(node.left);firstTraversal(node.right);return 0;}}
非递归实现：
public class MyTest {public ArrayList<Integer> fisrtTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();stack.add(root);TreeNode node = null;while (!stack.isEmpty()) {node = stack.pop();list.add(node.val);if (node.left != null) {stack.add(node.left);}if (node.right != null) {stack.add(node.right);}}return list;}}
2. 二叉树的中序遍历
递归实现：
public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int midTraversal(TreeNode node) {// 判断该节点是否存在if (node == null) {return 0;}firstTraversal(node.left);list.add(node.val);firstTraversal(node.right);return 0;}}
非递归实现：
利用栈实现。如图所示，向左斜下方向依次入栈，直达叶子节点；然后出栈两个（本身与其父节点）。
执行过程：
入栈：1、2、4 出栈：4、2
入栈：5 出栈：5
入栈：3、6 出栈：6、2
入栈：7 出栈：7
最终的中序遍历结果为：4、2、5、6、2、7
public class MyTest {public ArrayList<Integer> midTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list}Stack<TreeNode> stack = new Stack<>();stack.add(root);TreeNode node = root;while (!stack.isEmpty()) {if ((node != null) && (node.left != null)) {stack.add(node.left);node = node.left;} else {node = stack.pop();list.add(node.val);if (!stack.isEmpty()) {node = stack.pop();list.add(node.val);}node = node.right;}}return list;}}
3. 二叉树的后序遍历
递归实现：
public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int lastTraversal(TreeNode node) {// 判断该节点是否存在if (node == null) {return 0;}firstTraversal(node.left);firstTraversal(node.right);list.add(node.val);return 0;}}
非递归实现：
用两个栈（Stack1、Stack2）来实现。
将node压入Stack1，取出来把node的左右子节点，都压进Stack2；再把node压入Stack2。这样循环下去，Stack2的出栈顺序就是后续遍历。
public class MyTest {public ArrayList<Integer> lastTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.add(root);TreeNode node = null;while (!stack1.isEmpty()) {node = stack1.pop();if (node.left != null) {stack1.add(node.left);}if (node.right != null) {stack1.add(node.right);}stack2.add(node);}while (!stack2.isEmpty()) {list.add(stack2.pop().val);}return list;}}
4. 二叉树的广度优先遍历（层次遍历）
非递归实现（利用队列）：
public class MyTest {public ArrayList<Integer> levelTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);TreeNode node = null;while (!queue.isEmpty()) {node = queue.poll();list.offer(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return list;}}
