非递归二叉树遍历

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

前序遍历

public static void preorderTraversal(TreeNode root){
    if(root==null)
        return;
    TreeNode node = root;
    Stack<TreeNode> s = new Stack<>();
    s.push(node);
    while (node!=null||!s.isEmpty()){
        while (node!=null){
            System.out.println(node.val);
            s.push(node);
            node=node.left;
        }
        if(!s.isEmpty()){
            node = s.pop();
            node = node.right;
        }
    }
}

中序遍历

private static void middleorderTraversal(TreeNode root){
    if(root==null)
        return;
    Stack<TreeNode> s = new Stack<>();
    TreeNode node = root;
    while (node!=null||!s.isEmpty()){
        while (node!=null){
            s.push(node);
            node=node.left;
        }
        if (!s.isEmpty()){
            node=s.pop();
           // 与前序遍历不同的地方
            System.out.println(node.val);
            node=node.right;
        }
    }
}

后续遍历

private static void postorderTraversal(TreeNode root){
    if (root==null)
        return;
    Stack<TreeNode> s = new Stack<>();
    TreeNode node=root;
    // 需要记录上次输出的位置
    TreeNode lastVisit = root;
    while (node!=null||!s.isEmpty()){
        while (node!=null){
            s.push(node);
            node=node.left;
        }
        node = s.peek();
        if(node.right==null||node.right==lastVisit){
            System.out.println(node.val);
            s.pop();
            lastVisit = node;
            node = null;
        }else {
            node = node.right;
        }
    }
}