# LeetCode Medium 102. Binary Tree Level Order Traversal

tags: leetcode

問題

• Explore
• Problems

二分木が与えられた時, そのノードの値の層ごとの順番での走査を返せ(つまり, 左から右へ, 層ごとに)

解法1(recursive)

再帰的な構造を使います(無限回目)

• 返り値の二次元配列を用意します
  • この配列をretとしてret[d][i] = 深さdで左からi番目の要素という風に入れていきます
• 木の探索は再帰的にします
  • ノードがNULLならばその探索を終わりとします
  • retの1次元配列の数(1-indexed)が深さ(0-indexed)と同じならretに空の配列を追加します
• そして, ret[深さ]の配列にノードの値を追加します
• これは左の部分木と右の部分木に対しても行います

計算量

ノードの数を$n$とします

• 空間計算量
  • ノードの数だけ配列を作るので配列の分で$O(n)$です
  • 再帰の深さは最大$O(n)$で平均$O(\log(n))$
  • 合わせて$O(n)$です
• 時間計算量
  • 空間計算量と同様です

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
      def helper(node, ret, depth):
        if node == None:
          return
        if len(ret) == depth:
          ret.append([])
        
        ret[depth].append(node.val)
        helper(node.left, ret, depth+1)
        helper(node.right, ret, depth+1)
        
      ret = [[]]
      helper(root, ret, 0)
      return ret

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    helper(root, ret, 0);
    return ret;
  }
private:
  void helper(TreeNode* node, vector<vector<int>>& ret, int depth) {
    if (!node) {
      return;
    }
    if (ret.size() == depth) {
      ret.push_back(vector<int>());
    }
    
    ret[depth].push_back(node->val);
    helper(node->left, ret, depth+1);
    helper(node->right, ret, depth+1);
  }
};

解法2(queue)

今度はqueueで幅優先探索(BFS)をする解法です

queueはFIFOというデータ構造で最初に入れたデータを最初に取り出すというものです

二分木でQueueを使ってBFSをするのを図示するとしたのようになります

1. ノードをQueueに入れます
2. そのノードと繋がっているノードをQueueに入れます
3. Queueが空になるまで1と2を繰り返します

なぜFIFOでBFSが出来るのかを定性的に言います

FIFOだと最初に入れたノードから探索をするからです. 逆にLIFOであるStackを使うと最後に入れたノードから探索をするので深さ優先探索(DFS)となります

計算量

再帰をする必要がないので計算量は改善されます

• 空間計算量
  • $O(n)$
• 時間計算量
  • $O(n)$

Python

ここではdequeを使います

理由は単にPythonでのqueueの使い方がわからないからです. queueと同じ使い方をします

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

class Solution:
    def levelOrder(self, root):
      if not root:
        return []
      
      ret = []
      deq = deque([root])
      while deq:
        num_nodes = len(deq)
        cur = []
        for i in range(num_nodes):
          tmp = deq.popleft()
          cur.append(tmp.val)
          if tmp.left:
            deq.append(tmp.left)
          if tmp.right:
            deq.append(tmp.right)
        ret.append(cur)
        
      return ret

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    queue<TreeNode*> q;
    q.push(root);
    while (int n = q.size()) {
      vector<int> cur;
      cur.reserve(n);
      for (int i = 0; i < n; i++) {
        TreeNode* tmp = q.front();
        q.pop();
        if (tmp) {
          cur.push_back(tmp->val);
          q.push(tmp->left);
          q.push(tmp->right);
        }
      }
      if (cur.size()) 
      ret.push_back(cur);
    }
  
    return ret;
  }
};