(第25天)【leetcode题解】二叉树的层序遍历

目录

• 429、N叉树的层序遍历
• • 题目描述
  • 思路
  • 代码
• 515、在每个树行中找最大值
• • 题目描述
  • 思路
  • 代码
• 116、填充每个节点的下一个右侧节点指针
• • 题目描述
  • 思路
  • 代码
• 117、填充每个节点的下一个右侧节点指针II
• • 题目描述
  • 思路
  • 代码
• 104、二叉树的最大深度
• • 题目描述
  • 思路
  • 代码
• 111、二叉树的最小深度
• • 题目描述
  • 思路
  • 代码

429、N叉树的层序遍历

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

思路

• 将root节点放入队列
• 将root取出，并把它的val放入每一层的容器vec中，同时把它的子节点放入队列中
• 把每一层的节点值vec放入结果集res中
• 从队列中取出子节点，把它的值放入vec中，同时把它的子节点放入队列中
• 循环这个过程，知道队列中没有节点为止

代码

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> res;
        if (root != NULL) que.push(root);
        //
        while (!que.empty()) {
            int size = que.size();//每一层的节点数
            vector<int> vec;//存储每一层节点的值
            for (int i = 0; i < size; i++) {//把每一层节点的值都添加到vec中
                Node* node = que.front();
                que.pop();
                vec.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(vec);
        }
        return res;
    }
};

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

题目描述

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

思路

• 借助队列遍历每一层节点
• 在遍历每层的过程中，获得最大值

代码

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int max_val = INT_MIN;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node -> val > max_val) max_val = node -> val;
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            } 
            res.push_back(max_val);
        }
        return res;
    }
};

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

题目描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

思路

• 在层序遍历的基础上，每次都记录每一层的头部节点，然后在遍历地时候不断把前一个节点指向当前节点

代码

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            Node* nodePre;//前一个节点
            Node* node;//当前节点
            int size = que.size();
            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;//把前一个节点指向当前节点
                    nodePre = nodePre -> next;//移动指针到当前节点
                }
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            //nodePre -> next = NULL;
    }
        return root;
    }
};

117、填充每个节点的下一个右侧节点指针II

题目描述

给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。

思路

• 对比116题，从完美二叉树变成了普通二叉树。
• 在116题中采用的逻辑就是在遍历的过程中记录前一个节点，并把前一个节点的next指针指向当前节点。
• 这样的逻辑在本题也适用。

代码

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            Node* nodePre;//前一个节点
            Node* node;//当前节点
            int size = que.size();
            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;//把前一个节点指向当前节点
                    nodePre = nodePre -> next;//移动指针到当前节点
                }
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            nodePre -> next = NULL;//初始状态下，所有指针都被设置成了NULL，因此这行代码可以不加
    }
        return root;
    }
};

104、二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：3

思路

• 使用迭代法和层序遍历，二叉树的最大深度就是二叉树的层数

代码

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> que;
        int depth = 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            depth++;
            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);
            }

        }
        return depth;
    }
};

111、二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：2

思路

• 使用层序遍历。
• 再遍历每一层时，当找到一个节点左右子节点都为空时，表示这个节点是离根节点最近叶子节点。
• 当前层数就是二叉树的最小深度。

代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> que;
        int depth = 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            depth++;
            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);
                if (!node -> left && !node -> right) return depth;
            }
        }
        return depth;
    }
};