두 갈래 나무의 차원 반복 II---귀속과 교체

1477 단어 컴퓨터 기반
두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다)
예를 들어 두 갈래 나무[3,9,20,null,null,15,7],
  3
   / \
  9  20
    /  \
   15   7

아래에서 위로 올라가는 단계를 다음과 같이 되돌려줍니다.
[
  [15,7],
  [9,20],
  [3]
]

차례로 돌아가다
class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res=[]
        def deep(root,deepth):
            if not root:
                return 
            if len(res)==deepth:
                res.insert(0,[])
            res[-(deepth+1)].append(root.val)
            deep(root.left,deepth+1)
            deep(root.right,deepth+1)
            
        deep(root,0)
        return res

교체하다
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        from collections import deque
        if not root: return []
        queue = deque()
        queue.appendleft(root)
        res = []
        while queue:
            tmp = []
            n = len(queue)
            for _ in range(n):
                node = queue.pop()
                tmp.append(node.val)
                if node.left:
                    queue.appendleft(node.left)
                if node.right:
                    queue.appendleft(node.right)
            res.insert(0, tmp)
        return res

좋은 웹페이지 즐겨찾기