实现二叉树先序，中序和后序遍历

import java.util.*;
import java.io.*;

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

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = br.readLine().split(" ");
        int len = Integer.parseInt(params1[0]);
        Map<Integer,TreeNode> map = new HashMap<>();
        TreeNode head = new TreeNode(Integer.parseInt(params1[1]));
        map.put(Integer.parseInt(params1[1]),head);
        for(int i = 0;i < len; i++){
            String[] params2 = br.readLine().split(" ");
            int curVal = Integer.parseInt(params2[0]);
            int leftVal = Integer.parseInt(params2[1]);
            int rightVal = Integer.parseInt(params2[2]);
            TreeNode cur = map.getOrDefault(curVal,null);
            if(cur == null){
                cur = new TreeNode(curVal);
                map.put(curVal,cur);
            }
            if(leftVal != 0){
                cur.left = new TreeNode(leftVal);
                map.put(leftVal,cur.left);
            }
            if(rightVal != 0){
                cur.right = new TreeNode(rightVal);
                map.put(rightVal,cur.right);
            }
        }
        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        afterOrder(head);
    }
    
    /*
    先序遍历 用一个栈即可，因为栈是先入后厨，所以先压入左节点，在压入右节点，弹出的节点输出
    */
    public static void preOrder(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                TreeNode cur = stack.pop();
                System.out.print(cur.val + " ");
                if (cur.right != null){
                    stack.push(cur.right);
                }
                if (cur.left != null){
                    stack.push(cur.left);
                }
            }
            
        }
    }
    
    //中序遍历 213
    //先把左边界全部进栈，弹出一个节点，其有右节点，则在压入他的所有左边界
    public static void inOrder(TreeNode head){
        if (head != null){
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head !=null){
                if (head!=null){
                    stack.push(head);
                    head = head.left;
                }else {
                    //左树已经到头来，则可以pop了,然后pop时也可以观察有无右树
                    head = stack.pop();
                    System.out.print(head.val + " ");
                    head = head.right;
                }

            }
        }
    }
    
    //后序遍历231  --- 两个栈 第一个栈头左右 --》头右左 再用一个栈左右头
    public static void afterOrder(TreeNode head){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while(!stack1.isEmpty()){
            TreeNode cur = stack1.pop();
            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
            stack2.push(cur);
        }
        while(!stack2.isEmpty()){
            System.out.print(stack2.pop().val + " ");
        }
    }
}

import java.io.*;
import java.util.Scanner;
import java.util.Stack;
 class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }
public class Main{
    public static TreeNode createTree(BufferedReader br) throws Exception{
        String[] str = br.readLine().split(" ");
        int[] node = new int[str.length];
        for(int i = 0; i < str.length; i++){
            node[i] = Integer.parseInt(str[i]);
        }
           //构造该行输入对应节点
        TreeNode root = new TreeNode(node[0]);
        if( node[1] != 0 )  root.left = createTree(br);
        if( node[2] != 0 )  root.right = createTree(br);
        return root;
    }
    
    public static void main(String[] args) throws Exception{
//         Scanner sc = new Scanner(System.in);
//         String str = sc.nextLine();
//         TreeNode root = createTree(sc);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        TreeNode root = createTree(br);
        
        preOrder2(root);
        System.out.println();    
        infixOrder2(root);
        System.out.println(); 
        postOrder2(root);
        System.out.println(); 
    }
    // 递归实现
    public static void preOrder(TreeNode root){       
        if(root == null){
          return; 
        } 
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
        public static void infixOrder(TreeNode root){
        if(root == null){
          return; 
        }
        infixOrder(root.left);
        System.out.print(root.val+" ");  
        infixOrder(root.right);
    }
        public static void postOrder(TreeNode root){
         if(root == null){
          return; 
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");  
    }
    // 非递归实现
    //先压入头节点，再弹出它，压入他的右节点和左借点。重复
    public static void preOrder2(TreeNode root){
        Stack<TreeNode> st = new Stack();
        if(root == null){
            return;
        }
        st.push(root);
        while(!st.isEmpty()){
            root = st.pop();
            System.out.print(root.val+" ");
            if(root.right != null){
                st.push(root.right);
            }
            if(root.left != null){
                st.push(root.left);
            }
        }
    }
    public static void infixOrder2(TreeNode root){
        Stack<TreeNode> st = new Stack();
        if(root == null){
            return;
        }
        st.push(root);
        while(root.left != null){
            root = root.left;
            st.push(root);
        }
        while(!st.isEmpty()){
            root = st.pop();
            System.out.print(root.val+" ");
            if(root.right != null){
                root = root.right;
                st.push(root);
                while(root.left != null){
                    root = root.left;
                    st.push(root);
                }
            }
        }
    }
    public static void postOrder2(TreeNode root){
        Stack<TreeNode> st1 = new Stack();
        Stack<TreeNode> st2 = new Stack();
        // 先把shuju数据全压入s2
        if(root == null){
            return;
        }
        st1.push(root);
        while(!st1.isEmpty()){
            root = st1.pop();
            st2.push(root);
            if(root.left != null){
                st1.push(root.left);
            }
            if(root.right != null){
                st1.push(root.right);
            }
        }
        //依次弹出s2
        while(!st2.isEmpty()){
             root = st2.pop();
             System.out.print(root.val+" ");
        }
        
    }
}

import java.util.Scanner;
import java.util.HashSet;

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

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        if(sc.hasNextLine()){
            String[] input = sc.nextLine().split(" ");
            int n = Integer.parseInt(input[0]);
            Node root = new Node(Integer.parseInt(input[1]));
            HashSet<Node> set = new HashSet<Node>();
            set.add(root);
            
            for(int j= 0;j<n;j++){
                // build the binary tree
                String[] nodes = sc.nextLine().split(" ");
                int fatherValue = Integer.parseInt(nodes[0]);
                int leftValue = Integer.parseInt(nodes[1]);
                int rightValue = Integer.parseInt(nodes[2]);
                for(Node e:set){
                    if(e.value == fatherValue){
                        e.left = leftValue==0?null:new Node(leftValue);
                        e.right = rightValue==0?null:new Node(rightValue);
                        if(leftValue!=0){
                            set.add(e.left);
                        }
                        if(rightValue!=0){
                            set.add(e.right);
                        }
                        set.remove(e);
                        break;
                    }
                }
            }
            preOrder(root);
            System.out.print("\n");
            inOrder(root);
            System.out.print("\n");
            posOrder(root);
        }
    }
    
    public static void preOrder(Node d){
        if(d==null){
            return;
        }
        System.out.print(d.value);
        System.out.print(" ");
        if(d.left!=null){
            preOrder(d.left);
        }
        if(d.right!=null){
            preOrder(d.right);
        }
    }
    public static void inOrder(Node d){
        if(d==null){
            return;
        }
        if(d.left!=null){
            inOrder(d.left);
        }
        System.out.print(d.value);
        System.out.print(" ");
        
        if(d.right!=null){
            inOrder(d.right);
        }
    }
    public static void posOrder(Node d){
        if(d==null){
            return;
        }
        if(d.left!=null){
            posOrder(d.left);
        }
        if(d.right!=null){
            posOrder(d.right);
        }
        System.out.print(d.value);
        System.out.print(" ");
    }
    
}