💯 Daily LeetCode Challenge Day_02 - Binary Tree Level Order Traversal II

Account Login - LeetCode

---

문제

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

---

level 에 맞게 2개씩 짝짓는다.

DFS 로 풀다가 트리의 depth 별로 접근하니 BFS 인가 싶어서 

Queue를 쓰는 BFS 로 바꿨다가 어느 depth 지 판단하기 힘들어

다시 DFS 로 돌아와 depth를 저장하는 튜블 배열을 선언했다.

해당 배열을 정렬하면 제일 깊은 depth 를 얻을 수 있었고

해당 depth 만큼의 사이즈를 가진 answer를 리턴하면 되니

적절히 튜플값을 answer에 넣어주고

마지막에 reverse로 역순 처리 해주면 완성

Swift 여전히 적응이 안된다.

/**
 * 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 tmp : [(Int,Int)] = []
    
    func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {     
        if root == nil {
            return [[Int]]()
        }
        dfs(root!,0)
        
        tmp.sort(by: {$0.1 < $1.1})
        let size = tmp[tmp.count-1].1 + 1
        var answer : [[Int]] = Array(repeating: [], count: size)
        for item in tmp {
            answer[item.1].append(item.0)
        }
        
        return answer.reversed()
    }
    func dfs(_ node : TreeNode, _ level : Int) {
        tmp.append((node.val,level))
        if node.left != nil {
            dfs(node.left!,level + 1)
        }
        if node.right != nil {
            dfs(node.right!,level + 1)
        }
    }
}