前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

做到二叉树的题，由点及面，综合来复习一下二叉树遍历。

深度优先dfs：前序、中序、后序、其他

广度优先bfs：也就是层次遍历,其实也有很多各种变种不过理解透彻了可以融会贯通

深度优先dfs

递归遍历

递归前序遍历

public void preTree1(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preTree1(root.left);
            preTree1(root.right);
        }
    }

递归中序遍历

public void inTree1(TreeNode root) {
        if (root != null) {
            preTree1(root.left);
            System.out.print(root.val + " ");
            preTree1(root.right);
        }
    }

递归后序遍历

public void postTree1(TreeNode root) {
        if (root != null) {
            postTree1(root.left);
            postTree1(root.right);
            System.out.print(root.val + " ");
        }
    }

教科书式非递归遍历

教科书式遍历在数据结构书中有，前中后代码有点差距，前序和中序比较容易理解，后序相对复杂一点，代码风格不统一。

非递归前序遍历-教科书式

public void preTree2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pNode = root;
        while (pNode != null || !stack.isEmpty()) {
            while (pNode != null) {
                System.out.print(pNode.val + " ");
                stack.push(pNode);
                pNode = pNode.left;
            }
            if (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                pNode = node.right;
            }
        }
    }

非递归中序遍历-教科书式

public void inTree2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pNode = root;
        while (pNode != null || !stack.isEmpty()) {
            while (pNode != null) {
                stack.push(pNode);
                pNode = pNode.left;
            }
            if (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                System.out.print(node.val + " ");
                pNode = node.right;
            }
        }
    }

非递归后序遍历-教科书式

public LinkedList<Integer> postTree2(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return ans;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            //关键点
            ans.addFirst(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        return ans;
    }

创新式非递归遍历

以下为一种创新式，风格统一前中后遍历，比较容易记忆，有点类似分治，每一颗元子树排序好，并且有重合那么会导致整体都为有序。参考一下

有重合元素的局部有序一定能导致整体有序

这就是我得以统一三种更简单的非递归遍历方法的基本思想：有重合元素的局部有序一定能导致整体有序。如下这段序列，局部2 3 4和局部1 2 3都是有序的，但是不能由此保证整体有序。

而下面这段序列，局部2 3 4,4 5 6,6 8 10都是有序的，而且相邻局部都有一个重合元素，所以保证了序列整体也是有序的。

基于这种思想，我就构思三种非递归遍历的统一思想：不管是前序，中序，后序，只要我能保证对每个结点而言，该结点，其左子结点，其右子结点都满足以前序/中序/后序的访问顺序,整个二叉树的这种三结点局部有序一定能保证整体以前序/中序/后序访问，因为相邻的局部必有重合的结点，即一个局部的“根”结点是另外一个局部的“子”结点。

如下图，对二叉树而言，将每个框内结点集都看做一个局部，那么局部有A,A B C,B D E,D,E,C F,F,并且可以发现每个结点元素都是相邻的两个局部的重合结点。发觉这个是非常关键的，因为知道了重合结点，就可以对一个局部排好序后，通过取出一个重合结点过渡到与之相邻的局部进行新的局部排序。我们可以用栈来保证局部的顺序（排在顺序前面的后入栈，排在后面的先入栈，保证这个局部元素出栈的顺序一定正确），然后通过栈顶元素(重合元素)过渡到对新局部的排序，对新局部的排序会导致该重合结点再次入栈，所以当栈顶出现已完成过渡使命的结点时，就可以彻底出栈输出了（而这个输出可以保证该结点在它过渡的那个局部一定就是排在最前面的），而新栈顶元素将会继续完成新局部的过渡。当所有结点都完成了过渡使命时，就全部出栈了，这时我敢保证所有局部元素都是有序出栈，而相邻局部必有重合元素则保证了整体的输出一定是有序的。这种思想的好处是将算法与顺序分离，定义何种顺序并不影响算法，算法只做这么一件事：将栈顶元素取出，使以此元素为“根”结点的局部有序入栈，但若此前已通过该结点将其局部入栈，则直接出栈输出即可。

从实现的程序中可以看到：三种非递归遍历唯一不同的就是局部入栈的三行代码的先后顺序。所以不管是根->左->右,左->根->右,左->右->根,甚至是根->右->左,右->根->左,右->左->根定义的新顺序，算法实现都无变化，除了改变局部入栈顺序。

非递归前序遍历-创新式

public void preTree3(TreeNode root) {
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<>();
        stack.push(new Pair<>(root, false));
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek().getKey();
            boolean visited = stack.peek().getValue();
            stack.pop();
            if (node == null) {
                continue;
            }
            if (visited) {
                System.out.print(node.val + " ");
            } else {
                stack.push(new Pair<>(node.right, false));
                stack.push(new Pair<>(node.left, false));
                stack.push(new Pair<>(node, true));
            }
        }
    }

非递归中序遍历-创新式

public void inTree3(TreeNode root) {
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<>();
        stack.push(new Pair<>(root, false));
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek().getKey();
            boolean visited = stack.peek().getValue();
            stack.pop();
            if (node == null) {
                continue;
            }
            if (visited) {
                System.out.print(node.val + " ");
            } else {
                stack.push(new Pair<>(node.right, false));
                stack.push(new Pair<>(node, true));
                stack.push(new Pair<>(node.left, false));
            }
        }
    }

非递归后序遍历-创新式

public void postTree3(TreeNode root) {
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<>();
        stack.push(new Pair<>(root, false));
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek().getKey();
            boolean visited = stack.peek().getValue();
            stack.pop();
            if (node == null) {
                continue;
            }
            if (visited) {
                System.out.print(node.val + " ");
            } else {
                stack.push(new Pair<>(node, true));
                stack.push(new Pair<>(node.right, false));
                stack.push(new Pair<>(node.left, false));
            }
        }
    }

广度优先bfs

层次遍历

public void levelTree(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

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