彩灯装饰记录(合集)

彩灯装饰记录I

  vector<int> decorateRecord(TreeNode *root) {
    if (root == nullptr) return vector<int>{};

    vector<int> res;
    queue<TreeNode *> q;
    q.push(root);
    // BFS
    while (!q.empty()) {
      // 取出front
      auto front = q.front();
      res.push_back(front->val);
      q.pop();
      // 加入左右子节点
      if (front->left) q.push(front->left);
      if (front->right) q.push(front->right);
    }
    return res;
  }

彩灯装饰记录II

 // BFS，需要记录层数
  vector<vector<int>> decorateRecord(TreeNode *root) {
    if (root == nullptr) return {};
    vector<vector<int>> res;

    queue<TreeNode *> q;
    q.push(root);

    while (!q.empty()) {
      int level_size = q.size();

      vector<int> level_res;
      for (int i = 0; i < level_size; ++i) {
        auto front = q.front();
        q.pop();

        level_res.push_back(front->val);

        if (front->left) q.push(front->left);
        if (front->right) q.push(front->right);
      }
      res.push_back(level_res);
    }
    return res;
  }

彩灯装饰记录III

// 之字形打印
vector<vector<int>> decorateRecord(TreeNode *root) {
  if (root == nullptr) return {};
  vector<vector<int>> res;

  queue<TreeNode *> q;
  q.push(root);

  // 层序遍历
  bool reverse = false;
  while (!q.empty()) {
    int level_size = q.size();
    vector<int> level_res;
    for (int i = 0; i < level_size; ++i) {
      auto front = q.front();
      q.pop();
      if (reverse) {
        level_res.insert(level_res.begin(), front->val);
      } else {
        level_res.push_back(front->val);
      }
      // 左右子节点
      if (front->left) q.push(front->left);
      if (front->right) q.push(front->right);
    }
    reverse = !reverse;
    res.push_back(level_res);
  }
  return res;
}