두 갈래 나무의 오른쪽 보기
1863 단어 데이터 구조와 알고리즘
생각:
1) 이 문제는 매우 재미있다. 우선 명확해야 한다. 문제의 은밀한 의미는 두 갈래 나무의 각 층의 마지막 결점을 요구하는 것이다(왼쪽에서 오른쪽).
2) 두 갈래 나무가 차원을 나누기 때문에 차원을 이용하여 두 갈래 나무를 두루 돌아다녀야 한다.
3) 두 갈래 나무를 훑어볼 때 가장 중요한 내용은 현재 훑어보는 층이 어느 것이 마지막 결점인지 아는 것이다.
4) 변수를 설정하여 현재 층이 대열을 훑어볼 때 남은 결점서--this Level Remaind, 다음 층과 모두 몇 개의 결점수--next Level Has를 기록합니다. 그러면 대열이 나올 때마다this Level Remaind--, 새 노드가 들어갈 때마다next Level Has++.
5) 마지막으로thisLevelRemaind가 1일 경우 이 결점을 결과 집합에 추가합니다.
Java 코드:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List rightSideView(TreeNode root) {
List listQueue = new ArrayList();
List resultList = new ArrayList();
if (root == null)
return resultList;
int thisLevelRemaind = 1;
int nextLevelHas = 0;
listQueue.add(root);
while (!listQueue.isEmpty()) {
TreeNode headNode = listQueue.get(0);
if (headNode.left != null) {
listQueue.add(listQueue.get(0).left);
nextLevelHas++;
}
if (headNode.right != null) {
listQueue.add(headNode.right);
nextLevelHas++;
}
if (thisLevelRemaind == 1) {
resultList.add(headNode.val);
}
listQueue.remove(0);
thisLevelRemaind--;
if (thisLevelRemaind == 0) {
thisLevelRemaind = nextLevelHas;
nextLevelHas = 0;
}
}
return resultList;
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
