102. Binary Tree Level Order Traversal.md

102. Binary Tree Level Order Traversal

Difficulty : Meidum

---

similar as leetcode Daily Challenge on July 2rd, 2020. 107. Binary Tree Level Order Traversal II

---

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

---

Solution

• mine
  • Java
    • DFS & BFS Runtime: 1 ms, faster than 59.38%, Memory Usage: 40.7 MB, less than 7.81% of Java online submissions

      public List<List<Integer>> levelOrder(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(new ArrayList<>());
          }
          res.get(depth - 1).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(t);
              count++;
          }
      }
      

---