두 갈래 나무의 반복 (귀속과 비귀속)

1. 두 갈래 나무의 두루

2. 귀속 및 비귀속의 실현

import java.util.Stack;

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

    public void visit(TreeNode node){
        if(node != null){
            System.out.println(node.val);
        }
    }

    // 
    public void preOrder(TreeNode root){
        if(root != null){
            visit(root);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 
    public void preOrder_no(TreeNode root){
        Stack stack = new Stack();
        TreeNode current = root;
        while(current !=null || ! stack.isEmpty()){
            while(current != null){
                visit(current);
                stack.push(current);
                current = current.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                current = temp.right;
            }
        }
    }

    // 
    public void inOrder(TreeNode root){
        if(root != null){
            inOrder(root.left);
            visit(root);
            inOrder(root.right);
        }
    }

    // 
    public void inOrder_no(TreeNode root){
        Stack stack = new Stack();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                visit(temp);
                current = temp.right;
            }
        }
    }

    // 
    public void postOrder(TreeNode root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            visit(root);
        }
    }

    //  ， previsited 
    public void postOrder_no(TreeNode root){
        Stack stack = new Stack();
        TreeNode current = root;
        TreeNode privisited = null;
        while(current != null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.peek();
            if(current.right == null ||current.right == privisited){
                visit(current);
                stack.pop();
                privisited = current;
                current = null;

            }else{
                current = current.right;
            }
        }
    }

}