二叉树的迭代遍历（统一方法）

之后我们发现迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

中序遍历

分析

使用null，可以看出我们将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。总体思路：使用null中节点标记是否处理，在分别进行判断。

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
             * 统一迭代遍历（标记法）
             */
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                stack.pop();
                node = stack.peek();
                stack.pop();
                list.add(node.val);
            }
        }
        return list;
    }

前序遍历

代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        /**
             * 统一迭代遍历（标记法）
             */
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();    // 先将栈顶出栈，防止重复操作
                if (node.right != null) stack.push(node.right);  // 将右左中入栈
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null); // 表示遍历过该节点未访问
            }else {
                stack.pop();    // 先将空节点出栈
                node = stack.peek();    // 获取此时的节点
                stack.pop();    // 将当前节点出栈
                list.add(node.val); // 获取当前节点的结果
            }
        }
        return list;
    }

后序遍历

代码

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        /**
             * 统一迭代遍历（标记法）
             */
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();    // 先将栈顶出栈，防止重复操作
                stack.push(node);
                stack.push(null); // 表示遍历过该节点未访问
                if (node.right != null) stack.push(node.right);  // 将右左中入栈
                if (node.left != null) stack.push(node.left);
            }else {
                stack.pop();    // 先将空节点出栈
                node = stack.peek();    // 获取此时的节点
                stack.pop();    // 将当前节点出栈
                list.add(node.val); // 获取当前节点的结果
            }
        }
        return list;
    }