二叉树的右视图

  1. vector<int> rightSideView(TreeNode* root) {
  2.     if (root == NULL) return {};
  3.     vector<int> res;
  4.     queue<TreeNode *> q;
  5.     q.push(root);
  6.     while (!q.empty()) {
  7.         int _size = q.size();
  8.         for (int i = 0; i < _size; i++) {
  9.             TreeNode *cur = q.front();
  10.             q.pop();
  11.             if (cur->left) q.push(cur->left);
  12.             if (cur->right) q.push(cur->right);
  13.             if (i == (_size - 1)) res.push_back(cur->val);  // 将每一层的最后一个元素放进res数组中
  14.         }
  15.     }
  16.     return res;
  17. }

二叉树的层平均值

  1. vector<double> averageOfLevels(TreeNode* root) {
  2.     if (root == NULL) return {};
  3.     vector<double> res;
  4.     queue<TreeNode *> q;
  5.     q.push(root);
  6.     while (!q.empty()) {
  7.         int _size = q.size();
  8.         double sum = 0;
  9.         for (int i = 0; i < _size; i++) {
  10.             TreeNode *cur = q.front();
  11.             q.pop();
  12.             sum += cur->val;  // 每层的元素值相加
  13.             if (cur->left) q.push(cur->left);
  14.             if (cur->right) q.push(cur->right);
  15.         }
  16.         res.push_back(sum / _size);
  17.     }
  18.     return res;
  19. }

N叉树的层序遍历

  1. vector<vector<int>> levelOrder(Node* root) {
  2.     if (root == NULL) return {};
  3.     vector<vector<int> > res;
  4.     queue<Node *> q;
  5.     q.push(root);
  6.     while (!q.empty()) {
  7.         int _size = q.size();
  8.         vector<int> tmp(_size);
  9.         for (int i = 0; i < _size; i++) {
  10.             Node *node = q.front();
  11.             q.pop();
  12.             tmp[i] = node->val;
  13.             for (int i = 0; i < node->children.size(); i++) {
  14.                 // 将当前结点的各子结点放入队列中
  15.                 if (node->children[i]) q.push(node->children[i]);
  16.             }
  17.         }
  18.         res.push_back(tmp);
  19.     }
  20.     return res;
  21. }