BinaryTree,BFS_Leetcode_199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

• 각 depth의 가장 우측의 Treenode.val을 상위depth부터 하위depth로 array로 반환해야 함.
• 각 depth별 Treenode를 전부 알아야하기에, 전체 순환을 돌아야 한다고 생각
  • 약간의 꼼수?로 TreeNode의 갯수가 최대 100개이므로, 전체 순환을 돌아도 된다고 생각함.
• brutalForce에 가깝지만, queue를 사용하여 BFS한다. 이 때, 좌측 Treenode를 먼저 탐색한다
• 좌측 먼저 탐색하여 가장 마지막에 해당 Depth에 탐색된 값을 사용한다

정답코드

map을 [Int: [Int]]구조로 사용했는데, [Int]여도 문제 없었을 것 같다.

오히려 그러면 map -> sol로 변환하는 과정이 없어서 더 좋았을듯.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root else { return [] }
        var map: [Int: [Int]] = [:]
        var queue: [(TreeNode, Int)] = [(root,0)]
        map[0, default: []].append(root.val)
        while !queue.isEmpty {
            let (target, depth) = queue.removeFirst()
            let nextDepth = depth + 1
            if let lhs = target.left {
                map[nextDepth, default: []].append(lhs.val)
                queue.append((lhs, nextDepth))
            }
            if let rhs = target.right {
                map[nextDepth, default: []].append(rhs.val)
                queue.append((rhs, nextDepth))
            }
        }

        var sol = [Int](repeating: 0, count: (map.keys.max()! + 1))
        map.forEach { (key, values) in
            sol[key] = values.last!
        }
        return sol
    }
}