107. Binary Tree Level Order Traversal II.md

107. Binary Tree Level Order Traversal II

---

leetcode Daily Challenge on July 2rd, 2020.

leetcode-cn Daily Challenge on September 6th, 2020.

---

Difficulty : Easy

Related Topics : Tree、BFS

---

---

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

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

---

Solution

• mine
  • Java
    • DFS & BFS Runtime: 2 ms, faster than 18.87%, Memory Usage: 40.6 MB, less than 9.88% of Java online submissions

      // O(N)time
      // O(N)space
      // N is node count
      public List<List<Integer>> levelOrderBottom(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
          // dfs(root, res, 1);
          bfs(root, res);
          return res;
      }
      
      void dfs(TreeNode node, List<List<Integer>> res, int depth) {
          if (node == null) {
              return;
          }
          while (res.size() < depth) {
              res.add(0, new ArrayList<>());
          }
          res.get(res.size() - depth).add(node.val);
          if (node.left != null) dfs(node.left, res, depth + 1);
          if (node.right != null) dfs(node.right, res, depth + 1);
      }
      
      void bfs(TreeNode node, List<List<Integer>> res) {
          if (node == null) {
              return;
          }
          LinkedList<TreeNode>[] arr = new LinkedList[2];
          arr[0] = new LinkedList<>();
          arr[0].add(node);
          arr[1] = new LinkedList<>();
          int count = 0;
          while (!arr[count & 1].isEmpty()) {
              List<Integer> t = new ArrayList<>();
              while (!arr[count & 1].isEmpty()) {
                  TreeNode temp = arr[count & 1].removeFirst();
                  t.add(temp.val);
                  if (temp.left != null) arr[(count + 1) & 1].add(temp.left);
                  if (temp.right != null) arr[(count + 1) & 1].add(temp.right);
              }
              res.add(0, t);
              count++;
          }
      }
      

---