107. Binary Tree Level Order Traversal II

Problem Statement

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

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).

Example:

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

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

Input: root = [] Output: []

Solution Approach

The solution leverages a depth-first search (DFS) to traverse the tree and store the nodes’ values in a bottom-up level order.

Algorithm

1. Utilize a depth-first search to traverse the tree, maintaining the current node’s depth level.
2. During traversal, append node values to their respective level in the result list or initialize a new list for unseen levels.
3. By manipulating indices based on depth during traversal, the result list captures the bottom-up level order of the tree.

Implement

    class Solution:
      def dfs(node, level):
          if not node:
              return
          if level <= len(res):
              res[-level].append(node.val)
          else:
              res.insert(0,[node.val])
          dfs(node.left, level + 1)
          dfs(node.right, level + 1)
      res = []
      dfs(root, 1)
      return res
      

    
    

Twitter  facebook  Email