二叉树遍历的递归、非递归方法（前序、中序、后序，层序）——Java实现

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;
    }
}