二叉树的前序、中序、后序、层序遍历

1. 二叉树的前序遍历

前序遍历：根左右，即对于每一棵子树，先遍历其根节点，然后遍历其左子树，最后遍历其右子树

题目简述：给你二叉树的根节点root，返回它节点值的前序遍历。leetcode链接
思路一：递归遍历。递归函数体：先访问树根节点，然后递归访问左子树，再递归访问右子树。

    public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preTraversal(root,result);return result;}public void preTraversal(TreeNode root, List<Integer> result) {if(root == null) return;result.add(root.val);preTraversal(root.left, result);preTraversal(root.right, result);}

思路二：非递归遍历。使用栈。循环体：指针一直向左走，经过就访问并压入栈。左为null则pop一个已访问元素出来，迭代其右子树，如此循环，直到指针为null并且栈空。

    public List<Integer> preorderTraversal2(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.empty()) {while (root != null) {stack.push(root);result.add(root.val);//访问根节点root = root.left;//访问根节点的左子树}root = stack.pop();root = root.right;//访问右子树}return result;}

2. 二叉树的中序遍历

中序遍历：左根右，即对于每一棵子树，先遍历其左子树，然后遍历其根节点，最后遍历其右子树

题目简述：给定一个二叉树的根节点root，返回它的中序遍历。leetcode链接
思路一：递归遍历。先递归访问左子树，然后访问根节点，最后递归访问右子树。

    List<Integer> result = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {if(root == null) return result;inorderTraversal(root.left);result.add(root.val);inorderTraversal(root.right);return result;}

思路二：非递归遍历。使用栈。循环体：指针一直向左走，经过就压入栈，直到指向null后pop访问元素（此时其左子树必定为null或者已经pop访问过了），并根据左根右原则pop访问元素后要迭代其右子树

    public List<Integer> inorderTraversal2(TreeNode root) {Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();result.add(root.val);root = root.right;}return result;}

3. 二叉树的后序遍历

后序遍历：左右根，即对于每一棵子树，先遍历其左子树，然后遍历其右子树，最后遍历其根节点。对于一个节点，当其右孩子被访问后就接着被访问

题目简述：给你二叉树的根节点root，返回它节点值的后序遍历。leetcode链接
思路一：递归遍历。递归函数体：先递归访问左子树，再递归访问右子树，最后访问根节点。

    List<Integer> result = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {if(root == null) return result;postorderTraversal(root.left);postorderTraversal(root.right);result.add(root.val);return result;}

思路二：非递归遍历。使用栈。循环体：指针一直向左走，经过就压入栈，指向null后若栈顶元素右孩子不为null则迭代其右子树，若为null则pop访问栈顶元素。并根据左右根原则pop访问元素后,若其为父节点的左孩子，则迭代父节点的右子树，若为右孩子，则直接pop访问其父节点并重复此步骤。
注意：在一次循环中pop多次时要检查栈是否已空

    public List<Integer> postorderTraversal2(TreeNode root) {Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {//指针一直向左走，经过就压入栈stack.push(root);root = root.left;}if (stack.peek().right == null) {//若栈顶元素右孩子为null则pop栈顶元素root = stack.pop();result.add(root.val);while (!stack.isEmpty() && stack.peek().right == root) {//pop访问元素后，若其为右孩子，则直接pop访问其父节点，重复root = stack.pop();result.add(root.val);}}root = !stack.isEmpty() ? stack.peek().right : null;//否则迭代其右子树}return result;}

4. 二叉树的层序遍历

层序遍历：从上到下逐层从左向右遍历，也是广度优先遍历（BFS）

题目简述：给你二叉树的根节点root，返回其每一层的节点值序列。leetcode链接
思路：队列。在一次循环中，先记录队列中的元素数，然后按数量将队列中所有元素出队，每出队一个元素，则将其孩子节点入队
* 这样在每一次循环中，都出队一层元素，并入队下一层元素。循环结束条件即为队列为空，即最后一层元素已全部出队，下一层没有元素。

    public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if(root == null) return result;Queue<TreeNode> queue = new ArrayDeque<>();queue.add(root);//while(!queue.isEmpty()) {List<Integer> oneLevel = new ArrayList<>();int size = queue.size();for(int i=1;i <= size;i++) {TreeNode node = queue.remove();oneLevel.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}result.add(oneLevel);}return result;}