리트코드 leetCode binary-tree-right-side-view

문제 : https://leetcode.com/problems/binary-tree-right-side-view/

Binary Tree Right Side View - LeetCode

 

풀이 :  모든 레벨에서 가장 오른쪽에 있는 노드만을 찾아 저장해야 하는 문제.

① 재귀로 구현 > 오른쪽 노드를 탐색하는 부분을 먼저 수행하면서 값을 저장하도록 위치를 조정함.

   - 오른쪽 노드 탐색

   - 왼쪽 노드를 탐색

② 더 이상 자식 노드가 없으면서 저장된 값의 길이가 현재 위치 레벨과 같으면 값을 저장

저장된 값의 길이 == 현재 위치 레벨이면 현재 위치가 가장 오른쪽 노드임을 의미함. 

*TreeNode를 소스에서 재구현해준 이유는 TreeNode에 노드가 하나도 없는 경우( [] )와 노드 0 이 들어온 경우 [0]를 구분하기 위해서임. int로 구현되어 있는 val를 Integer로 변환하여 null을 인지할 수 있도록 함. 

(int는 Default값이 0이기 때문에, 노드의 값이 0으로 셋팅된 것인지, null인지를 구분할 수 없음)

 

구현  JAVA

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;


public class TreeNode {
      Integer val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
     public List<Integer> rightSideView(TreeNode root) {

        List<Integer> answer = new ArrayList<>();
        getAnswer(answer, root,0);

        return answer;
    }

    private void getAnswer(List<Integer> answer, TreeNode now, int level) {

        if (Objects.isNull(now)) {
            return;
        }
        if(answer.size()==level){
            answer.add(now.val);
        }
        getAnswer(answer, now.right, level+1);
        getAnswer(answer, now.left, level+1);

    }
    
}

 

테스트케이스

Input	Output
[0,1,2,null,3,4,null,null,5,9,null,null,6,10,null]	[0,2,4,9,10]
[1,2,3,4]	[1,3,4]
[1,2]	[1,2]