[LeetCode] 199. Binary Tree Right Side View(Kotlin)

[LeetCode] 199. Binary Tree Right Side View(Kotlin)

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

풀이

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

import java.util.Deque

class Solution {
    fun rightSideView(root: TreeNode?): List<Int> {
        // rightSide[i]: 깊이가 i인 right side 노드
        val rightSide = mutableListOf<Int>()

        // 너비 기반 탐색, Pair<노드, 노드의 깊이>
        val q = ArrayDeque<Pair<TreeNode?, Int>>()
        q.addLast(Pair(root, 0))
        while(!q.isEmpty()){
            val curPair = q.first()
            val curNode = curPair.first
            val curDepth = curPair.second
            q.removeFirst()

            if(curNode == null) continue

            if(rightSide.size <= curDepth) rightSide.add(curNode.`val`)
            else rightSide[curDepth] = curNode.`val`

            if(curNode.left != null) q.addLast(Pair(curNode.left,curDepth+1))
            if(curNode.right != null) q.addLast(Pair(curNode.right,curDepth+1))
        }

        return rightSide.toList()
    }
}