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);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 노트-107 두 갈래 트리 레이아웃 II두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다) 사고방식 1: 전체적인 사고방식은 나무의 모든...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.