199. 두 갈래 나무의 오른쪽 보기(중등 문제)

제목 설명: 두 갈래 나무를 정하고 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다.
예:
입력: [1,2,3,null, 5,null, 4] 출력: [1,3,4] 설명:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/binary-tree-right-side-view저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.해법:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            Queue<TreeNode> next = new LinkedList<>();
            int last = 0;
            while (!que.isEmpty()) {
                TreeNode cur = que.poll();
                last = cur.val;
                if (cur.left != null) {
                    next.add(cur.left);
                }
                if (cur.right != null) {
                    next.add(cur.right);
                }
            }
            list.add(last);
            que.addAll(next);
        }
        return list;
    }
}

사고방식 개술: 차원이 두루 흐르고list는 각 층의 마지막 결점의 값을 기록한다.하나의 넥스트 대기열로 현재 결점의 다음 층(즉 좌우 아이)을 기록합니다. 이렇게 하면 현재 대기열에 영향을 주지 않습니다. 매번 결점이 튀어나올 때마다last값을 업데이트합니다. 마지막 튀어나오는 것은 반드시 현재 결점의 가장 오른쪽입니다.que가 비어 있을 때,next 대기열은 다음 층의 모든 노드를 기록합니다.모든 넥스트의 결점을que에 추가하면 됩니다.
물론 추가 넥스트 대기열을 사용하지 않아도 됩니다.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int last = 0;
            int size = que.size();
            while (size-- > 0) {
                TreeNode cur = que.poll();
                last = cur.val;
                if (cur.left != null) {
                    que.add(cur.left);
                }
                if (cur.right != null) {
                    que.add(cur.right);
                }
            }
            list.add(last);
        }
        return list;
    }
}