DFS_LeetCode_Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/

이론적으로 알고만 있던 DFS, BFS를 첫번째로 풀어봤다.

이전에 이론을 간단히 공부하고 간단한 알고리즘 문제를 시도해봤지만, 무참히 실패했었는데, 그 때엔 재귀를 사용할 생각을 못했기때문!
이번엔 재귀를 사용하여 풀이를 진행했다.

 

특이점으로는, LeetCode는 문제 자체에 class를 줘서 전역변수를 사용하여 진행했다. 재귀하는 함수가 return하는 내용이 없단 뜻!

코드

/**
 * 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 {
    var solArray: [String] = []
    
    func sumNumbers(_ root: TreeNode?) -> Int {
        tmp(root, history: "")
        
        return solArray.reduce(0, { $0 + Int($1)!})
    }
    
    
    /// direction : true == left, false= right
    func tmp(_ input: TreeNode?, history: String) {
        let present = String(input!.val)
        let nextHistory = history + present
        
        if input?.left == nil && input?.right == nil {
            solArray.append(nextHistory)
            return
        }
        
        if input?.left != nil {
            tmp(input!.left, history: nextHistory)
        }
        
        if input?.right != nil {
            tmp(input!.right, history: nextHistory)
        }
    }
}

간단 코드 설명

1. 현재 노드의 값을 String으로 변환

2. 매개변수 history와 1.의 값을 합쳐 재귀에 사용될 tmp에 매개변수로 전달할 nextHistory값 생성

3. 현재 노드의 다음 노드가 없을 경우, 전역Array에 현재 노드.val이 포함된 nextHistory를 append

4. 다음 노드의 유무를 확인하여 재귀 실행