题解 | 二叉树的三种遍历方式非递归版本汇总

前序遍历

我们利用栈的特性，先将根节点压栈，每次都是从栈中弹出一个，然后将这个节点的右、左孩子压栈。

注意：压栈时，一定要先压右孩子，然后是左孩子

    public int[] preorderTraversal (TreeNode root) {
        if(root == null){
            return new int[]{};
        }
        Stack<TreeNode> st = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<>();
        st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.pop();
            list.add(node.val);
		  // 先压右孩子
            if(node.right != null){
                st.push(node.right);
            }
            if(node.left != null){
                st.push(node.left);
            }
        }
        int[] res = new int[list.size()];
        
        for(int i = 0; i< list.size(); i ++){
            res[i] = list.get(i).intValue();
        }
        return res;
    }

后序遍历

后续遍历只需要在前序遍历的模版上稍作修改即可。

前序遍历 是 中左右，我们调整左右两个节点的压栈顺序，左孩子先入栈，则最终得到的顺序是中右左，然后反转这个结果就是后续遍历左右中

import java.util.*;

public class Solution {
   
    public int[] postorderTraversal (TreeNode root) {
        if(root == null){
            return new int[]{};
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.pop();
            list.add(node.val);
            if(node.left != null){
                st.push(node.left);
            }
            if(node.right != null){
                st.push(node.right);
            }
        }
        Collections.reverse(list);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size() ; i ++){
            res[i] = list.get(i).intValue();
        }
        return res;
    }
}

中序遍历

中序遍历时，我们就不能使用前序遍历的模版了。

在前序遍历中，因为要访问的节点和要处理的节点是一致的，都是中间节点。

但是对于中序遍历来说，我们处理的元素顺序与访问的不一致，还需要借助指针来实现。

用一个指针来表示当前访问的节点，不断的将左孩子压栈，一直到底，然后右孩子压栈

    public int[] inorderTraversal (TreeNode root) {
        if(root == null){
            return new int[]{};
        }

        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        TreeNode curr = root;
        while(curr != null || !st.isEmpty()){
            while(curr != null){
                st.push(curr);
                curr = curr.left;
            }
            curr = st.pop();
            list.add(curr.val);
            curr = curr.right;
        }


        int[] res = new int[list.size()];
        for(int i = 0; i < list.size() ;i ++){
            res[i] = list.get(i).intValue();
        }
        return res;
    }