.leetcode(199. Binary Tree Right Side View)

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

 

1. 2022.03.29 시도

소요시간: 6분(구상 1분, 코딩 5분, recursion ), 4분(iteration)

// recursion
class Solution {
    private List<Integer> result;
    public List<Integer> rightSideView(TreeNode root) {
        result = new ArrayList<>();
        recursion(root, 0);
        return result;
    }
    
    public void recursion(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        if (result.size() == depth) {
            result.add(root.val);
        }
        recursion(root.right, depth+1);
        recursion(root.left, depth+1);
    }
}

// iteration
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int len = queue.size();
            for (int i=0; i<len; i++) {
                TreeNode node = queue.poll();    
                if (i == 0) {
                    result.add(node.val);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }   
        }

        return result;
    }
}

 

풀이 접근 과정

문제가 오른쪽 부분은 다 읽으라는 것으로 이해했다.

depth에 맞게 하나씩 오른쪽만 읽으면 되겠다 싶었다. 파라미터를 주면 전역변수 안써도 되지만 원리가 파괴되는건 아니기에 그대로 작업했다.

 

느낀점

• recusrion과 iteration 방식으로 풀었는데 다른 tree문제와 크게 다르지 않다.
• 최근에 풀었던 https://silvergoni.tistory.com/entry/leetcode-114-Flatten-Binary-Tree-to-Linked-List 와 비슷한 문제다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형