二叉树的迭代遍历

递归的本质是栈，使用迭代遍历就是使用栈来实现。

前序遍历

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。此时出栈的顺序才为中左右。

代码：

   public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       if (root == null) {
           return list;
       }
       // 先将root入栈
       stack.push(root);
       // 循环直到不为空
       while (!stack.isEmpty()) {
           // 先将栈顶的节点出栈
           TreeNode treeNode = stack.pop();
           // 获取元素
           list.add(treeNode.val);
           // 先将右孩子入栈，出栈时右孩子再后面出栈
           if (treeNode.right != null) {
               stack.push(treeNode.right);
           }
           // 后将左孩子入栈，出栈时先出栈
           if (treeNode.left != null) {
               stack.push(treeNode.left);
           }
       }
       return list;
   }

后序遍历

后序遍历和前序遍历刚好相反，所以调整入栈顺序为中左右，此时出栈即为中右左，得到的遍历二叉树为中右左，此时将结果进行反转即为左右中。

代码：

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return list;
    }
    // 先将root入栈
    stack.push(root);
    // 循环直到不为空
    while (!stack.isEmpty()) {
        // 先将栈顶的节点出栈
        TreeNode treeNode = stack.pop();
        // 获取元素
        list.add(treeNode.val);
        // 先将右孩子入栈，出栈时右孩子再后面出栈
        if (treeNode.left != null) {
            stack.push(treeNode.left);
        }
        // 后将左孩子入栈，出栈时先出栈
        if (treeNode.right != null) {
            stack.push(treeNode.right);
        }
    }
    // 此时遍历的是中右左，反转之后即为左右中
    Collections.reverse(list);
    return list;
}

中序遍历

因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

此时中序和前序，后序有所不同。

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了不同的原因就是处理节点的顺序和打印节点的顺序不是一致的。例如：一开始将中间节点入栈，但却不打印中间节点，造成了不一致，所以不能简单的将正在处理的节点val打印出来。

代码：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return list;
    }
    TreeNode cur = root;  // 用来记录当前的节点
    while (cur != null || !stack.isEmpty()) {    // 此时没有先将root入栈，所以循环还需要cur判断
        if (cur != null) {
            stack.push(cur);    // 将当前节点入栈
            cur = cur.left;     // 继续向左孩子遍历
        } else {
            cur = stack.pop();  // 左孩子为空后，此时出栈
            list.add(cur.val);  // 打印该节点的值
            cur = cur.right;    // 再遍历右孩子，如果右孩子为空，跳到中节点的上一个节点
        }
    }
    return list;
}