BinaryTreeTraversal

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTreeTraversal {
    // 非递归先序遍历
    public List<Integer> preorderTraverse(TreeNode root){
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while ( cur!=null || !stack.isEmpty() ){
            while ( cur!=null ){
                ret.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            if ( !stack.isEmpty() ){
                cur = stack.pop().right;
            }
        }
        return ret;
    }

    // 递归先序遍历
    public void preorderTraverse(TreeNode root, List<Integer> list){
        if ( root==null ){
            return;
        }else{
            list.add(root.val);
            preorderTraverse(root.left, list);
            preorderTraverse(root.right, list);
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorderTraverse(root, list);
        return list;
    }


    // 非递归中序遍历
    public List<Integer> inorderTraverse(TreeNode root) {
        if ( root==null ){
            return null;
        }else{
            TreeNode tmp = root;
            Stack<TreeNode> stack = new Stack<>();
            Set<TreeNode> visitedNode = new HashSet<>();
            List<Integer> list = new ArrayList<>();
            stack.push(tmp);
            visitedNode.add(tmp);
            while ( !stack.isEmpty() ) {
                tmp = stack.peek();
                while ( !visitedNode.contains(tmp.left) && tmp.left != null) {
                    stack.push(tmp.left);
                    visitedNode.add(tmp.left);
                    tmp = tmp.left;
                }
                tmp = stack.pop();
                list.add(tmp.val);
                if ( !visitedNode.contains(tmp.right) && tmp.right != null ){
                    stack.push(tmp.right);
                    visitedNode.add(tmp.right);
                }
            }
            return list;
        }
    }

    // 递归中序遍历
    public void inorderTraverse(TreeNode root, List<Integer> list){
        if ( root==null ){
            return;
        }else{
            inorderTraverse(root.left, list);
            list.add(root.val);
            inorderTraverse(root.right, list);
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorderTraverse(root, list);
        return list;
    }

    // 非递归后序遍历
    public List<Integer> postorderTraverse(TreeNode root){
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if ( root!=null ) {
            stack.push(root);
        }
        TreeNode cur, pre=null;
        while ( !stack.isEmpty() ){
            cur = stack.peek();
            if ( (cur.left==null && cur.right==null) || (pre!=null && (pre==cur.left || pre==cur.right)) ){  // 如果当前结点没有孩子结点或者孩子节点都已被访问过
                ret.add(cur.val);
                pre = stack.pop();
            }else{
                if ( cur.right!=null ){
                    stack.push(cur.right);
                }
                if ( cur.left!=null ){
                    stack.push(cur.left);
                }
            }
        }
        return ret;
    }

    // 递归后序遍历
    public void postorderTraverse(TreeNode root, List<Integer> list){
        if ( root==null ){
            return;
        }else{
            postorderTraverse(root.left, list);
            postorderTraverse(root.right, list);
            list.add(root.val);
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postorderTraverse(root, list);
        return list;
    }

    public static void printList(List<Integer> list){
        for ( int i=0; i<list.size(); i++ ){
            System.out.print(list.get(i)+"\t");
        }
        System.out.println();
    }

    public static void main(String[] args){
        TreeNode[] nodes = new TreeNode[10];
        for ( int i=0; i<nodes.length; i++ ){
            nodes[i] = new TreeNode(i);
        }
        nodes[0].left = nodes[1];
        nodes[0].right = nodes[2];
        nodes[1].left = nodes[3];
        nodes[1].right = nodes[4];
        nodes[2].left = nodes[5];
        nodes[3].right = nodes[6];
        nodes[4].left = nodes[7];
        nodes[4].right = nodes[8];
        nodes[5].left = nodes[9];

        BinaryTreeTraversal btt = new BinaryTreeTraversal();
        List<Integer> preorderRet_Rec = btt.preorderTraversal(nodes[0]);
        List<Integer> preorderRet_NonRec = btt.preorderTraverse(nodes[0]);
        System.out.println("先序遍历二叉树");
        printList(preorderRet_Rec);
        printList(preorderRet_NonRec);

        List<Integer> inorderRet_Rec = btt.inorderTraversal(nodes[0]);
        List<Integer> inorderRet_NonRec = btt.inorderTraverse(nodes[0]);
        System.out.println("中序遍历二叉树");
        printList(inorderRet_Rec);
        printList(inorderRet_NonRec);

        List<Integer> postorderRet_Rec = btt.postorderTraversal(nodes[0]);
        List<Integer> postorderRet_NonRec = btt.postorderTraverse(nodes[0]);
        System.out.println("后序遍历二叉树");
        printList(postorderRet_Rec);
        printList(postorderRet_NonRec);
    }
}