검지 Offer - 지그재그 순서로 두 갈래 트리 인쇄(Java 구현)

제목 설명:


함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
사고방식 분석: 1. 두 개의 창고stack1,stack2를 빌려야 한다.2. stack1은 홀수층의 노드 수를 기록하는 데 사용되고, stack2는 짝수층의 노드 수를 기록하는 데 사용된다.3. 시작할 때 먼저 머리 노드를 stack1에 넣고 stack1의 노드를 튀기는 동시에 튀어나온 노드의 좌우 하위 노드를 stack2에 저장하고 (왼쪽 노드를 저장하고 오른쪽 노드를 저장하며) 튀어나온 노드를list 집합에 저장합니다.stack1이 비어 있으면 stack2의 요소가 튀어나오기 시작하고 튀어나온 노드의 좌우 하위 노드를 stack1에 저장합니다(오른쪽 노드를 저장하고 왼쪽 노드를 저장합니다). 튀어나온 노드는list 집합에 저장합니다.
코드는 다음과 같습니다.
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
// :
// 
public class Solution {
    public ArrayList > Print(TreeNode pRoot) {
        
        ArrayList> alist = new ArrayList<>();
        if(pRoot == null){
            return alist;
        }
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        stack1.push(pRoot);
        while(!stack1.empty() || !stack2.empty()){
            ArrayList list = new ArrayList<>();
            if(!stack1.empty()){
                while(!stack1.empty()){
                TreeNode temp = stack1.pop();
                list.add(temp.val);
                if(temp.left != null){
                    stack2.push(temp.left);
                }
                if(temp.right != null){
                    stack2.push(temp.right);
                }
            }
                alist.add(list);
            }
            else{
                while(!stack2.empty()){
                TreeNode temp = stack2.pop();
                list.add(temp.val);
                if(temp.right != null){
                    stack1.push(temp.right);
                }
                if(temp.left != null){
                    stack1.push(temp.left);
                }
            }
            alist.add(list);
            }
        }
        return alist;
    }
}

좋은 웹페이지 즐겨찾기