层序遍历

二叉树的层序遍历102. 二叉树的层序遍历 - 力扣（LeetCode）

二叉树的右视图. - 力扣（LeetCode）

填充右节点指针117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

#include "bits/stdc++.h"

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

using namespace std;

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        queue<TreeNode *> q;
        vector<vector<int>> res;
        TreeNode *ceng = root;
        if (root == nullptr) return res;
        q.emplace(root);
        vector<int> part;
        while (!q.empty()) {
            TreeNode *temp = q.front();
            q.pop();
            if (ceng == temp) {
                if (ceng != root) res.push_back(part);
                part.clear();
                ceng = nullptr;
            }
            if (ceng == nullptr && temp->left != nullptr) {
                ceng = temp->left;
            } else if (ceng == nullptr && temp->right != nullptr) {
                ceng = temp->right;
            }
            if (temp->left != nullptr) q.emplace(temp->left);
            if (temp->right != nullptr) q.emplace(temp->right);
            part.push_back(temp->val);
        }
        res.push_back(part);
        return res;
    }
};

class Solution2 {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        queue<TreeNode *> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();   //与我的解法不一样，他注意到计数下一层的结点数可以不用确定一层有多少个，而我的解法是标记每层的开端
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode *node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

class Solution3 {
public:
    vector<int> rightSideView(TreeNode *root) {
        queue<TreeNode *> q;
        if (root != nullptr) q.emplace(root);
        vector<int> res;
        while (!q.empty()) {
            int size = q.size(); //q.size() is changing.So you may use 'size'.
            for (int i = 0; i < size; i++) {
                TreeNode *temp = q.front();
                q.pop();
                if (temp->left) q.emplace(temp->left);
                if (temp->right) q.emplace(temp->right);
                if (i == size - 1) res.push_back(temp->val);
            }
        }
        return res;
    }
};

class Node {
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
            : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution4 {
public:
    Node *connect(Node *root) {
        queue<Node*> q;
        if(root) q.emplace(root);
        while(!q.empty()){
            int size=q.size();
            if(size<2){
                Node* temp=q.front();
                q.pop();
                temp->next= nullptr;
                if(temp->left) q.emplace(temp->left);
                if(temp->right) q.emplace(temp->right);
            } else if(size>=2) {
                Node *l1=q.front();
                q.pop();
                if(l1->left) q.emplace(l1->left);
                if(l1->right) q.emplace(l1->right);
                Node *l2=q.front();
                q.pop();
                if(l2->left) q.emplace(l2->left);
                if(l2->right) q.emplace(l2->right);
                l1->next=l2;
                for(int i=0;i<size-1;i++){
                    Node* l3 = i==size-2? nullptr:q.front();
                    if(l3!= nullptr){
                        if(l3->left) q.emplace(l3->left);
                        if(l3->right) q.emplace(l3->right);
                        q.pop();
                    }
                    l1=l2;
                    l2=l3;
                    l1->next=l2;
                }

            }
        }
        return root;
    }
};