二叉树的遍历（迭代）

用Deque和linkedList代替stack

上一篇文章是一种递归方法。:
单击跳转递归方法

本文是一种迭代方法

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List inorderTraversal(final TreeNode root) {
        final List res = new ArrayList<>();
        final Deque stack = new LinkedList<>();
        TreeNode p = root;
        while (stack.size() != 0 || p != null) {
            while (null != p) {
                stack.addLast(p);
                p = p.left;
            }
            p = stack.removeFirst();
            res.add(p.val);
            p = p.right;
        }
        return res;
    }
}

stack.addLast 是因为 为了模拟堆叠， 是将元素添加到堆栈的顶部。 所以不要在这里混淆， 堆栈是后进先出， 栈顶是stack[0]