LeetCode - 두 갈래 나무의 오른쪽 보기
1747 단어 Leet Code 연습
두 갈래 나무를 정해서 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다.
예:
: [1,2,3,null,5,null,4]
: [1, 3, 4]
:
1
생각: 제목을 보자마자 얼떨떨하다가 예시를 보고 반응했다. 이것은 바로 두 갈래 나무의 각 층의 마지막 원소를 되돌려주는 것이 아니냐. 두 갈래 나무의 층이 두루 흐르는 것을 연상하기 때문에 각 층의 마지막 원소를 표시하면 해결된다.
차원 반복은 대열을 빌려 실현해야 한다. 대열의'선진 선출'특성을 이용하여 차원 반복을 편리하게 실현할 수 있다.
그럼 바로 제 코드를 붙여주세요. LeetCode에 3ms가 표시되고 메모리가 비교적 많이 사용됩니다. 35.1MB입니다. 공간을 시간을 바꾸는 셈이죠.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List rightSideView(TreeNode root) {
List list = new ArrayList<>();
// , list
if(root == null)
return list;
//
ArrayDeque queue = new ArrayDeque<>();
queue.add(root);
//curLayer
//nextLayer ,( )
int curLayer = 1, nextLayer = 0;
while(!queue.isEmpty()){
TreeNode node = queue.pop();
curLayer--;
if(node.left != null){
queue.add(node.left);
nextLayer++;
}
if(node.right != null){
queue.add(node.right);
nextLayer++;
}
// ,
if(curLayer == 0){
list.add(node.val);
curLayer = nextLayer;
nextLayer = 0;
}
}
return list;
}
}
자, 이상은 제 생각과 코드입니다.
위의 코드가 가장 좋은 것이 아닙니다. 만약 당신들이 더욱 우수한 생각을 가지고 있다면, 지도를 환영합니다!