第144、94、145、102题 二叉树遍历（迭代）

二叉树遍历分为四种遍历，前序遍历、中序遍历、后序遍历和层序遍历。在本文中，将使用迭代的的方法来对四类遍历进行实现。

这里在题目方面和四种遍历方法的原理方面不赘述，详见：

第144、94、145、102题 二叉树遍历http://mp.weixin.qq.com/s?__biz=Mzk0MjM5ODM2NQ==&mid=2247483700&idx=1&sn=08eb1c7ee9cf11b62083c3ed8ad39a0a&chksm=c2c28fc6f5b506d0763829d5ae98d0644da50a93a73dff0f980d973d3acbfefbb8bef84c739f&scene=21#wechat_redirect

144. 前序遍历：

通过迭代来实现对于递归栈的模拟，代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list  = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root != null)stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            if(root!=null){
                list.add(root.val);
                stack.push(root.right);
                stack.push(root.left);
            }
        }
        return list;
    }
}

先解释一下这个代码，我们定义了一个栈来对遍历中的情况进行存储，因为要实现的是前序遍历，所以我们将root压入栈，再将root结点的右结点压入栈内，再将root结点的左结点压入栈内，为什么要这样做呢？因为我们要实现的先序遍历，优先级：

根结点>左结点>右结点，而栈的特点是先入后出，后入先出，所以应该先将右结点压入再压入左结点，直到栈空了迭代停止，那如果左结点和右结点为null怎么办呢，如果为null的话我们还是将其压入栈内，但就只弹出，不将值赋给list即可，即如第8行所示，加上弹出结点不为null，才对其左右结点进行操作。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40.1 MB, 在所有 Java 提交中击败了5.19%的用户

94. 中序遍历：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list  = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty() || root!=null){
            if(root!=null){
                stack.push(root);
                root = root.left;
            }
            else{
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
}

因为中序遍历的结点优先级为：左结点>根结点>右结点，所以在一个结点存在左节点时需要一直寻找下去，找到结点为null时开始弹出存储入list，然后若该结点还不存在右结点，即为叶子结点，再弹出，将其父结点存储入list，然后再对其右结点进行判断。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.8 MB, 在所有 Java 提交中击败了34.65%的用户

145. 后序遍历：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list  = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        while(!stack.isEmpty() || root!=null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right==null||root.right==pre)
            {
                list.add(root.val);
                pre = root;
                root = null;
            }
            else{
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
}

在这里说一下个人认为比较难理解的一个点，为什么需要pre来保存我们上一个点，因为在局部根结点时，我们不知道是从左结点还是右结点返回而来的，如果是右结点返回来的，则无需再对其右结点进行操作，我当时看到这了纠结的点在于，如果我们root赋值给了pre，又把root赋值为null，那if(root.right==null||root.right==pre)不就是重复判断了吗，因为我把root当成了其右结点，但不是，root 只是一个变量名，将root赋值为null，并不意味着把其右结点赋值为null。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.6 MB, 在所有 Java 提交中击败了53.77%的用户

102. 层序遍历：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if(root != null)queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> temp= new ArrayList<Integer>();
            for(int i = 0; i < len ; i++){
                root = queue.remove();
                temp.add(root.val);
                if(root.left != null){
                    queue.add(root.left);
                }
                if(root.right != null){
                    queue.add(root.right);
                }
            }
            list.add(temp);
        }
        return list;
    }
}

使用了一个LinkedList，每次循环的时候采用remove()将表内的数据按先入先出的方式输出，作为一层，然后将下一层的元素添加进去，保证每次循环中，表内的元素都是同一层的。

执行用时：1 ms, 在所有 Java 提交中击败了57.37%的用户

内存消耗：41.9 MB, 在所有 Java 提交中击败了7.44%的用户