当前位置：网站首页>420-二叉树的层序遍历2（429. N 叉树的层序遍历、515.在每个树行中找最大值、116.填充每个节点的下一个右侧节点指针、104.二叉树的最大深度、111.二叉树的最小深度）

420-二叉树的层序遍历2（429. N 叉树的层序遍历、515.在每个树行中找最大值、116.填充每个节点的下一个右侧节点指针、104.二叉树的最大深度、111.二叉树的最小深度）

2022-06-25 06:42:00 【liufeng2023】

429. N 叉树的层序遍历

在这里插入图片描述

class Solution {
    
public:
    vector<vector<int>> levelOrder(Node* root) {
    
        vector<vector<int>> res;
        queue<Node*> que;

        if (root != nullptr) que.push(root);

        while (!que.empty())
        {
    
            vector<int> temp;
            int size = que.size();

            for (int i = 0; i < size; i++)
            {
    
                Node* node = que.front();
                que.pop();

                temp.push_back(node->val);

                for (int i = 0; i < (node->children.size()); i++)
                {
    
                    if (node->children[i]) que.push(node->children[i]);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

在这里插入图片描述

515.在每个树行中找最大值

在这里插入图片描述

class Solution {
    
public:
    vector<int> largestValues(TreeNode* root) {
    
        vector<int> res;
        queue<TreeNode*> que;

        if (root != nullptr) que.push(root);

        while (!que.empty())
        {
    
            int size = que.size();
            int temp = INT32_MIN;

            for (int i = 0; i < size; i++)
            {
    
                TreeNode* node = que.front();
                que.pop();

                temp = (node->val > temp) ? node->val : temp;
                if (node->left)  que.push(node->left);
                if (node->right) que.push(node->right);
            }
            res.push_back(temp);
        }
        return res;
    }
};

在这里插入图片描述

116.填充每个节点的下一个右侧节点指针

在这里插入图片描述

class Solution {
    
public:
    Node* connect(Node* root) {
    
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
    
            int size = que.size();
            // vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) {
    
                if (i == 0) {
    
                    nodePre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
    
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;

    }
};

在这里插入图片描述

104.二叉树的最大深度

在这里插入图片描述

class Solution {
    
public:
    int maxDepth(TreeNode* root) {
    
        queue<TreeNode*> que;
        int res = 0;
        if (root)    que.push(root);

        while (!que.empty())
        {
    
            int size = que.size();

            for (int i = 0; i < size; i++)
            {
    
                TreeNode* node = que.front();
                que.pop();

                if (node->left)  que.push(node->left);
                if (node->right)  que.push(node->right);
            }
            res++;
        }
        return res;
    }
};

在这里插入图片描述

111.二叉树的最小深度

在这里插入图片描述

class Solution {
    
public:
    int minDepth(TreeNode* root) {
    
        queue<TreeNode*> que;
        int res = 0;

        if (root)    que.push(root);

        while (!que.empty())
        {
    
            int size = que.size();
            res++;
            for (int i = 0; i < size; i++)
            {
    
                TreeNode* node = que.front();
                que.pop();

                if (node->left == nullptr && node->right == nullptr)   return res;
                if (node->left)  que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return res;
    }
};