力扣练习题(2024/5/2)

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; // 返回翻转后的根节点
    }
};

上一篇:Ftrans文件外发系统 构建安全可控文件外发流程


下一篇:ue引擎游戏开发笔记(26)——处理角色死亡敌人仍攻击bug