二叉树迭代遍历

一、前序遍历

前序遍历为NLR，所以每次先处理根结点，将右孩子加入栈，再加入左孩子。这样才能得到中左右的出栈序列。

public List<Integer> preorder_2(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;  
    }
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.push(root);
    while(!deque.isEmpty()) {
        TreeNode node = deque.pop();
        result.add(node.val);
        if(node.right != null) {
            deque.push(node.right);
        }
        if(node.left != null) {
            deque.push(node.left);
        }
    } 
    return result;
}

统一风格迭代:先弹出结点，再按照RLN添加到栈中。

class Solution {
    public List<Integer> preorder_2(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop(); 
                if (node.right!=null) deque.push(node.right);
                if (node.left!=null) deque.push(node.left);
                deque.push(node);          
                deque.push(null);
            } else { 
                deque.pop();    
                node = deque.peek();  
                deque.pop();
                result.add(node.val); 
            }
        }
        return result;
    }
}

二、中序遍历

借助指针访问结点，栈则来处理结点上的元素。

public List<Integer> inorder_2(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null){
        return result;
    }
    Deque<TreeNode> deque = new ArrayDeque<>();
    TreeNode p = root,;
    while (p != null || !deque.isEmpty()){
       if (p != null){
           deque.push(p);
           p = p.left;
       }else{
           p = deque.pop();
           result.add(p.val);
           p = p.right;
       }
    }
    return result;
}

统一风格迭代法：先弹出结点，再按照RNL添加到栈中。

class Solution {
    public List<Integer> inorder_2(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop(); 
                if (node.right!=null) deque.push(node.right);
                deque.push(node);          
                deque.push(null);
                if (node.left!=null) deque.push(node.left);
            } else { 
                deque.pop();    
                node = deque.peek();  
                deque.pop();
                result.add(node.val); 
            }
        }
        return result;
    }
}

三、后序遍历

后序遍历为LRN，可以通过先序遍历的代码调整为NRL再反转结果得到LRN。

public List<Integer> postorder_2(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null){
        return result;
    }
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.push(root);
        while (p != null || !deque.isEmpty()){
            TreeNode node = deque.pop();
            result.add(node.val);
            if (node.left != null){
                deque.push(node.left);
            }
            if (node.right != null){
                deque.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

统一风格迭代写法：先弹出结点，再按照NRL添加到栈中。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.peek();
            if (node != null) {
                deque.pop(); 
                deque.push(node);          
                deque.push(null);
                if (node.right!=null) deque.push(node.right);
                if (node.left!=null) deque.push(node.left);
            } else { 
                deque.pop();    
                node = deque.peek();  
                deque.pop();
                result.add(node.val); 
            }
        }
        return result;
    }
}