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

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

• 树中节点的数量在 [0, 212 - 1] 范围内
• -1000 <= node.val <= 1000

解题思路：

 1. 首先定义一个节点结构体，包含节点的值、左节点、右节点和指向同一层下一个节点的指针。  2. 使用队列que存储每一层的节点，初始时将根节点放入队列中。

 3. 进入while循环，直到队列为空。每次循环表示处理一层节点。

 4. 在每层节点的循环中，先获取当前层节点数size，然后遍历当前层所有节点。

5. 若当前是该层的第一个节点（i == 0），则将该节点作为当前层的头结点，并弹出队列。

6. 否则，将当前节点与前一个节点连接（nodePre->next = node），并维护前一个节点为当前节点。

 7. 检查当前节点是否有左右子节点，有则加入队列中，以便后续处理下一层节点。

 8. 这样循环直到处理完当前层所有节点，最后一个节点的next指针指向NULL。

9. 返回根节点，表示连接完成。 

代码：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) {
            que.push(root); // 将根节点放入队列中
        }
        while (!que.empty()) {
            int size = que.size(); // 当前层的节点个数
            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;
    }
};

2二叉树的最大深度

简单

相关标签

相关企业

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

思路：

1. 首先判断根节点是否为空，如果为空直接返回深度0。
2. 定义一个整型变量maxDepth用于记录最大深度，初始化为0。
3. 使用队列que进行层次遍历，将根节点放入队列中。
4. 进入while循环，直到队列为空。每次循环表示处理一层节点。
5. 在每层节点的循环中，先获取当前层节点数size，然后遍历当前层所有节点。
6. 每次循环遍历时，深度加一。
7. 取出队列中的节点，如果节点有左孩子，则将左孩子节点加入队列；如果节点有右孩子，则将右孩子节点加入队列。
8. 当处理完当前层所有节点后，继续下一轮while循环，直到遍历完所有节点。
9. 最后返回最大深度。

代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr)  return 0; // 如果根节点为空，返回深度0
        int maxDepth = 0; // 初始化最大深度为0
        queue<TreeNode*> que; // 定义队列用于层次遍历
        que.push(root); // 将根节点放入队列中
        while(!que.empty()){
            int size = que.size(); // 当前层的节点个数
            maxDepth++; // 深度加一
            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 maxDepth; // 返回最大深度
    }
};

3二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

思路：

1. 首先判断根节点是否为空，如果为空直接返回深度0。
2. 定义一个整型变量minDepth用于记录最小深度，初始化为0。
3. 使用队列que进行层次遍历，将根节点放入队列中。
4. 进入while循环，直到队列为空。每次循环表示处理一层节点。
5. 在每层节点的循环中，先获取当前层节点数size，然后遍历当前层所有节点。
6. 每次循环遍历时，深度加一。
7. 取出队列中的节点，如果节点有左孩子，则将左孩子节点加入队列；如果节点有右孩子，则将右孩子节点加入队列。
8. 当遍历到叶子节点时，即节点没有左右子节点，直接返回当前深度作为最小深度。
9. 继续遍历完所有节点后，最后返回最小深度。

代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0; // 如果根节点为空，返回深度0
        queue<TreeNode*> que; // 定义队列用于层次遍历
        que.push(root); // 将根节点放入队列中
        int minDepth = 0; // 初始化最小深度为0
        while(!que.empty()){
            int size = que.size(); // 当前层的节点个数
            minDepth++; // 深度加一
            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 minDepth;
                }
            }
        }
        return minDepth; // 返回最小深度
    }
};

4翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

1递归思路：

1. 首先判断根节点是否为空，如果为空直接返回。
2. 交换根节点的左右子节点，实现翻转操作。
3. 递归调用翻转函数分别对左子树和右子树进行翻转操作。
4. 最后返回翻转后的根节点。

代码：

class Solution {
public:
    // 翻转二叉树函数，输入根节点，返回翻转后的根节点
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return 0; // 如果根节点为空，直接返回
        swap(root->left, root->right); // 交换左右子节点
        invertTree(root->left); // 递归翻转左子树
        invertTree(root->right); // 递归翻转右子树
        return root; // 返回翻转后的根节点
    }
};

2迭代法思路：

1. 首先判断根节点是否为空，如果为空直接返回。
2. 创建一个栈用于辅助操作，将根节点压入栈中。
3. 循环遍历栈，每次取出栈顶节点，交换其左右子节点。
4. 如果当前节点有左子节点，将左子节点压入栈中；如果有右子节点，将右子节点压入栈中。
5. 循环直到栈为空，完成整个二叉树的翻转操作。

代码：

class Solution {
public:
    // 翻转二叉树函数，输入根节点，返回翻转后的根节点
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return 0; // 如果根节点为空，直接返回
        stack<TreeNode*> st; // 定义一个栈用于辅助翻转操作
        st.push(root); // 将根节点压入栈中
        while (!st.empty()) { // 当栈不为空时循环执行
            TreeNode* node = st.top(); // 取出栈顶节点
            st.pop(); // 弹出栈顶节点
            swap(node->left, node->right); // 交换当前节点的左右子节点
            if (node->left) st.push(node->left); // 如果有左子节点，压入栈中
            if (node->right) st.push(node->right); // 如果有右子节点，压入栈中
        }
        return root; // 返回翻转后的根节点
    }
};