두 갈래 나무의 귀속 및 비귀속 두루

앞의 순서가 두루 미치다.

   //  
    private static void pre(TreeNode root){
        if(root == null){
            return;
        }

        System.out.println(root.val);
        pre(root.left);
        pre(root.right);
    }

    //  
    private static void pre1(TreeNode root){
        if(root == null){
            return;
        }

        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while(!s.isEmpty()){
            TreeNode node = s.pop();
            System.out.println(node.val);

            if(node.right != null){
                s.push(node.right);
            }
            if(node.left != null){
                s.push(node.left);
            }
        }
    }

중순으로 두루 다니다.

//  
    private static void in(TreeNode root){
        if(root == null){
            return;
        }

        in(root.left);
        System.out.println(root.val);
        in(root.right);
    }

    //  
    private static void in1(TreeNode root){
        if(root == null){
            return;
        }

        Stack<TreeNode> s = new Stack<>();

        while(!s.isEmpty() || root != null){
            if(root != null){
                s.push(root);
                root = root.left;
            }else{
                root = s.pop();    //  ， root 
                System.out.println(root.val);
                root = root.right;
            }
        }
    }

후순이 두루 다니다

 //  
    private static void post(TreeNode root){
        if(root == null){
            return;
        }

        post(root.left);
        post(root.right);
        System.out.println(root.val);
    }

    //  
    private static void post1(TreeNode root){
        if(root == null){
            return;
        }

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        s1.push(root);
        while(!s1.isEmpty()){
            TreeNode node = s1.pop();

            s2.push(node);
            if(node.left != null){
                s1.push(node.left);
            }

            if(node.right != null){
                s1.push(node.right);
            }
        }

        while(!s2.isEmpty()){
            TreeNode node = s2.pop();
            System.out.println(node.val);
        }
    }