旭的小窝

107. Binary Tree Level Order Traversal II

 
  • 2023年 06月16日

Promble

link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/

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

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Input: root = [1]
Output: [[1]]

Input: root = []
Output: []

Approach 1

BFS

Thought

  1. judge if root is None
  2. def queue:deque, from collections.deque
  3. append root to queue
  4. def output:list to store the result
  5. while queue
    1. def noeds_in_curr_level:list to store the current level nodes
    2. def length is len(queue) # the length will update, 1.
    3. loop in range(length)
      1. popleft from queue, to curr_node
      2. append curr_node.val to nodes_in_curr_level
      3. if curr_node.left: queue.append(curr_node.left)
      4. if curr_node.right: queue.append(curr_node.right)
    4. output.append(nodes_in_curr_level)
  6. return reversed(output)

📓the leetcode def the TreeNode, so we should notice the structure of this class.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque 

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = deque()
        queue.append(root)
        output = []
        
        while queue:
            nodes_in_curr_level = []
            length = len(queue)

            for _ in range(length):
                curr_node = queue.popleft()
                nodes_in_curr_level.append(curr_node.val)
                # print(nodes_in_curr_level)
                # print(queue)
                if curr_node.left:
                    queue.append(curr_node.left)

                if curr_node.right:
                    queue.append(curr_node.right)
                # print(queue)

            output.append(nodes_in_curr_level)

        return reversed(output)
搜索