leetcode 노트 - 199두 갈래 나무의 오른쪽 보기

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

   1            

사고방식: 인터넷에서 찾은 신의 코드, 원문 링크:https://blog.csdn.net/mine_song/article/details/70213524
처음에 나는 오른쪽 보기가 오른쪽 나무의 모든 오른쪽 노드라고 생각했는데 실제로는 그렇지 않았다. 각 층의 가장 오른쪽 노드였다.광도 우선 검색을 사용하여 트리를 층별로 훑어보고 각 층의 맨 오른쪽 노드를 기록합니다.
이것은 내가 다시 할 때 잘 이해했다. 사용 차원을 두루 훑어보고 각 층의 노드 개수를 기록하고 마지막 노드를 결과에 넣는 것을 생각했다.하지만 층이 두루 흐르는 것에 대해 나는 아직 잘 알지 못한다...이거 좀 봐야겠다.
코드:
public List rightSideView(TreeNode root) {         List ret = new ArrayList<>();         if (root == null)             return ret;         bfs(root, ret);         return ret; } private void bfs(TreeNode root, List ret) {Queue q = new LinkedList<>(), q.add(root);//차원을 두루 돌아다니며 이 층의 결점 개수만 기록하면 intcurNum = 1;/다음 층의 노드 수 intnextNum = 0;while (! q.isEmpty () {TreeNode node = q.poll ();             if (curNum == 1)                 ret.add(node.val);             curNum--;             if (node.left != null) {                 q.offer(node.left);                 nextNum++;             }             if (node.right != null) {                 q.offer(node.right);                 nextNum++;             }             if (curNum == 0) {                 curNum = nextNum;                 nextNum = 0;             }         }     }  
가장 빠른 코드 실행:
이것은 마치 앞의 순서대로 역귀해법인 것 같습니다. level이size와 같을 때 가장 오른쪽 노드라는 것을 설명합니다. 직접 접속하면 됩니다.
class Solution {
        private List result = new ArrayList<>();

    public List rightSideView(TreeNode root) {
        getList(root, 0);
        return result;
    }

    private void getList(TreeNode node, int level) {
        if (node != null) {
            if (level >= result.size()) {
                result.add(node.val);
            }
            level++;
            getList(node.right, level);
            getList(node.left, level);
        }
    }
}

좋은 웹페이지 즐겨찾기