level - medium
[문제 내용]
주어진 바이너리 트리를 오른쪽에서 바라봤을때, 위에서 아래로 순서대로 표시된 노드의 값을 반환하라.
[example 1]
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4][example 2]
Input: root = [1,null,3]
Output: [1,3][example 3]
Input: root = []
Output: [][해결 방법]
재귀 방식을 이용해 해당 문제를 풀었고,
먼저 가장 오른쪽에 있는 노드를 방문하여 null이 아닌 가장 오른쪽에 있는 노드 값을 저장하고
해당 tree의 깊이를 index로 하여 해당 값을 저장하고
오른쪽에서 왼쪽으로 탐색을 진행하며 왼쪽을 탐색할때 해당 tree의 깊이에 이미 값이 저장되어 있다면 값을 저장하지 않고 계속 더 깊이 탐색을 진행한다.
class Solution {
fun rightSideView(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
findRightSide(0, root, result)
return result
}
fun findRightSide(depth: Int, root: TreeNode?, result: MutableList<Int>) {
if(root == null) return
if(result.size-1 < index) {
result.add(depth, root.`val`)
}
findRightSide(depth+1, root.right, result)
findRightSide(depth+1, root.left, result)
}
}
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}