Easy

두 갈래 나무를 지정하여 아래에서 위층으로 훑어보는 노드 값을 되돌려줍니다. (왼쪽에서 오른쪽으로, 잎에서 뿌리까지)
Example: 두 갈래 나무[3,9,20,null,null,15,7], 3/9 20/15 7 반환: [[15,7],[9,20,],[3]
이 문제는 전형적인 DFS(depth-first search) 알고리즘 문제입니다.귀속 방법을 사용할 수 있습니다.

루트 노드 level은 0입니다. 루트 노드의 값을 찾고 응답res를 추가합니다

루트 노드 레벨을 업데이트하고 루트 노드의 왼쪽 지점과 오른쪽 지점을 각각 루트 노드를 찾습니다..

여기서 관건은 루트 노드의 level을 통해 좌우가 아래로 흐를 때 동기적으로 추진할 수 있도록 제어하는 것이다.이 문제는 아래에서 위로 출력하기 때문에 결과에 대한 reverse가 필요합니다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(root,0,res)
        return res
        
    def dfs(self, root, level, res):
        if root:
            if len(res) < level + 1:
                res.insert(0,[])
            res[-(level+1)].append(root.val)
            self.dfs(root.left,level+1,res)
            self.dfs(root.right,level+1,res)

dfs+stack

다음은 stack을 직접 활용하는 또 다른 해결 방안입니다.

def levelOrderBottom2(self, root):
    stack = [(root, 0)]
    res = []
    while stack:
        node, level = stack.pop()
        if node:
            if len(res) < level+1:
                res.insert(0, [])
            res[-(level+1)].append(node.val)
            stack.append((node.right, level+1))
            stack.append((node.left, level+1))
    return res

bfs + queue

다음은 제3자 해결 방법입니다.queue를 이용하세요.

def levelOrderBottom(self, root):
    queue, res = collections.deque([(root, 0)]), []
    while queue:
        node, level = queue.popleft()
        if node:
            if len(res) < level+1:
                res.insert(0, [])
            res[-(level+1)].append(node.val)
            queue.append((node.left, level+1))
            queue.append((node.right, level+1))
    return res