LeetCode-103- 두 갈래 나무의 톱날 모양 층계 반복

두 갈래 나무의 톱날 모양 층계가 두루 다니다

제목 설명: 두 갈래 나무를 정하고 노드 값을 되돌려주는 톱날 모양의 층계를 반복합니다.(즉, 먼저 왼쪽에서 오른쪽으로, 다시 오른쪽에서 왼쪽으로 다음 층을 훑어보며, 이와 같이 층과 층 사이를 교체하여 진행한다.)
예시 설명은 LeetCode 홈페이지를 참조하십시오.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/probl... 저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
해법1: 대기열과 창고를 이용하여 두 갈래 나무를 훑어보다
대열의 특징은 선진적인 선출이고 창고의 특징은 후진적인 선출이기 때문에 대열과 창고를 이용하여 두 갈래 나무를 옮겨다니며 톱니 모양을 옮겨다니는 구체적인 과정은 다음과 같다.

우선, 루트가 비어 있으면 비어 있는 목록으로 바로 돌아갑니다

만약에 루트가 비어 있지 않으면 하나의 대기열 nodes를 성명하고 루트 노드를 대기열에 추가하고result를 성명하며boolean 형식의 변수directionFlag를 성명하고directionFlag가true일 때 왼쪽에서 오른쪽으로 창고에 노드를 넣는다.directionFlag가false일 때 오른쪽에서 왼쪽으로 노드를 넣고 노드의 노드를 훑어봅니다. 훑어보는 과정은 다음과 같습니다.

우선count로 현재 대기열에 있는 노드의 수량을 기록한다. 즉, 현재 층 노드의 수량이고vals는 현재 노드의 값을 기록하고 창고temp를 설명한다

nodes에서count 개 노드를 순서대로 추출하고 해당하는 노드 값을 vals에 넣는다. 또한 현재 노드의 좌우 하위 노드가 비어 있지 않으면directionFlag에 따라 왼쪽에서 오른쪽으로 순서대로 할지 오른쪽에서 왼쪽으로 순서대로temp에 넣을지 판단한다.결과result에 vals를 추가합니다.

창고temp의 원소를 모두 꺼내서 nodes에 넣습니다..

노드가 비어 있을 때까지 노드의 노드를 반복합니다

마지막으로result를 되돌려줍니다. 즉, 톱날 모양의 층계를 두루 훑어본 결과입니다

설명: 해결 방법은 LeetCode-102- 두 갈래 나무의 층계를 훑어보는 것과 유사하다.

import java.util.*;

public class LeetCode_103 {
    public static List> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List> result = new ArrayList<>();
        Queue nodes = new LinkedList<>();
        nodes.add(root);
        //  directionFlag true ， ； directionFlag false ， 
        boolean directionFlag = true;
        while (!nodes.isEmpty()) {
            int count = nodes.size();
            List vals = new ArrayList<>();
            Stack temp = new Stack<>();
            while (count > 0) {
                TreeNode curNode = nodes.poll();
                vals.add(curNode.val);
                if (!directionFlag) {
                    if (curNode.right != null) {
                        temp.push(curNode.right);
                    }
                    if (curNode.left != null) {
                        temp.push(curNode.left);
                    }
                } else {
                    if (curNode.left != null) {
                        temp.push(curNode.left);
                    }
                    if (curNode.right != null) {
                        temp.push(curNode.right);
                    }
                }
                count--;
            }
            //  
            while (!temp.isEmpty()) {
                nodes.add(temp.pop());
            }
            //  
            directionFlag = !directionFlag;
            result.add(vals);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);


        for (List integers : zigzagLevelOrder(root)) {
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

[일일 우송]
공부하는 적은 자신의 만족이다. 조금만 열심히 공부하려면 자만하지 않아야 한다!