[검지 offer] 지그재그 순서로 두 갈래 나무 프린트하기

제목 설명

함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
 
 
제목 링크:
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 
 
 

package com.sunshine.OFFER66_SECOND;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Stack;

public class A59_Print {

    @Test
    public void test(){
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        ArrayList> print = Print(n1);
        for (ArrayList arrayList : print) {
            for (Integer integer : arrayList) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }
    }



    public ArrayList> Print(TreeNode pRoot) {
        ArrayList> ans = new ArrayList<>();
        if(null == pRoot){
            return ans;
        }
        Stack s1=new Stack<>();
        s1.push(pRoot);
        Stack s2=new Stack<>();
        while(!s1.empty()||!s2.empty()){
            ArrayList row=new ArrayList<>();
            if(!s1.empty()){
                while(!s1.empty()){
                    TreeNode node = s1.pop();
                    row.add(node.val);
                    if(null!=node.left){
                        s2.push(node.left);
                    }
                    if(null!=node.right){
                        s2.push(node.right);
                    }
                }
            }else{
                while(!s2.empty()){
                    TreeNode node = s2.pop();
                    row.add(node.val);
                    if(null!=node.right){
                        s1.push(node.right);
                    }
                    if(null!=node.left){
                        s1.push(node.left);
                    }
                }
            }
            ans.add(row);
        }
        return ans;
    }
}