代码随想录_刷题记录_第四次

news/2024/9/29 12:25:13 标签: 笔记, leetcode, 算法

二叉树 — 理论基础

种类：

  • 满二叉树（所有层的节点都是满的，k：深度 节点数量：2^k - 1）
  • 完全二叉树（除了最后一层，其余层全满，并且最后一层从左到右连续）
  • 二叉搜索树（对于每一个父节点来说，左子树的所有节点都小于父节点，右子树的所有节点都大于父节点 时间复杂度 ： log(n) ）
  • 平衡二叉搜索树（左子树和右子树的高度差不能大于1 时间复杂度：log(n)

存储方式：

  • 链式存储（左指针、右指针）
  • 线式存储（数组 父节点 i，左子节点 2i + 1，右子节点 2i + 2）

遍历方式：

  • 深度优先搜索：递归方式实现（前序、中序、后序）、迭代法（使用栈）
  • 广度优先搜索：一层一层的去遍历（迭代法，使用队列）（层序遍历）

前序：中左右 中序：左中右 后序：左右中

定义方法：

struct TreeNode{
	int value;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int val) : value(val) left(NULL) right(NULL) {}
}

**二叉树节点的深度：**从根节点到该节点的最长简单路径边的条数（前序递归求深度）

**二叉树节点的高度：**从该节点到叶子节点（左右子节点都为空）的最长简单路径边的条数（后序递归求高度）

前序遍历求深度，后序遍历求高度

二叉树 — 递归遍历

递归遍历的三步骤：

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑

前序遍历

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

**题目要求：**给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 ：

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

img

思路：

  1. 确定参数（根节点、vec数组）和返回值（void）

    void traversal(TreeNode* cur, vector<int>& vec)

  2. 确定终止条件（深度优先搜索，cur == NULL return）

    if (cur == NULL) return;

  3. 确定单层递归的逻辑

    vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

解法：

  • C++
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == NULL) return;
        vec.push_back(cur->val);      // 中
        traversal(cur->left, vec);    // 左
        traversal(cur->right, vec);   // 右
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);   // 传入根节点和存放结果的数组
        return result;
    }
};

中序遍历

题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

  • C++
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == NULL) return;
        traversal(cur->left, vec);    // 左
        vec.push_back(cur->val);      // 中
        traversal(cur->right, vec);   // 右
    }


    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);   // 传入根节点和存放结果的数组
        return result;
    }
};

后序遍历

题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

  • C++
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == NULL) return;
        traversal(cur->left, vec);    // 左
        traversal(cur->right, vec);   // 右
        vec.push_back(cur->val);      // 中
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);   // 传入根节点和存放结果的数组
        return result;
    }
};

二叉树 — 迭代遍历

**递归的实现：**每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因

所以，我们使用栈也可以实现二叉树的前中后序遍历

前序遍历

**思路：**用栈存放节点，用数组存放结果

先将根节点放入栈中，进入循环直到栈为空，取出栈顶结点作为中间节点（中左右），放入这个节点的右子节点，再放入这个节点的左子节点（取出时是先取左子节点）（如果为空则不放入）

解法：

  • C++
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
    	vector<int> result;
        stack<TreeNode*> st;
        if(root == NULL) return result;
        st.push(root);   // 先将根节点放入栈中
        while(!st.empty()){
            TreeNode* cur = st.top();   // 取出栈顶结点作为这次的中间节点
            st.pop();           
            result.push_back(cur->val);
            if(cur->right) st.push(cur->right);   // 向栈中放入右子节点，如果为空则不放入
            if(cur->left)  st.push(cur->left);    // 向栈中放入左子节点
        } 
        return result;
    }
};

后序遍历

**思路：**跟前序遍历相同，只不过调转了左右子节点入栈的顺序，此时输出的结果为 中右左，所以需要调换顺序输出 左右中

解法：

  • C++
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
    	vector<int> result;
        stack<TreeNode*> st;
        if(root == NULL) return result;
        st.push(root);   // 先将根节点放入栈中
        while(!st.empty()){
            TreeNode* cur = st.top();   // 取出栈顶结点作为这次的中间节点
            st.pop();
            result.push_back(cur->val);
            if(cur->left)  st.push(cur->left);    // 向栈中放入左子节点
            if(cur->right) st.push(cur->right);   // 向栈中放入右子节点，如果为空则不放入
        }   
        reverse(result.begin(), result.end());    // 中右左 -> 左右中
        return result;
    }
};

中序遍历

思路：

写法与前序遍历、后序遍历不同，因为前序遍历和后序遍历的顺序是中左右、中右左（最后反转），要访问的元素和要处理的元素顺序是一致的，但是中序遍历 左中右 处理顺序和访问顺序是不一致的

所以，在使用迭代法写中序遍历的时候，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

解法：

  • C++
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            if(cur){   // 向该子节点的左子节点一直遍历，直到为空
                st.push(cur);   // 将所有节点放入栈中
                cur = cur->left;
            }else{   // 若已经遍历到底
                cur = st.top();   // 取出栈顶元素（最左子节点）
                st.pop();
                result.push_back(cur->val);   // 放入左子节点
                cur = cur->right;   // 取出右子节点重复操作
            }
        }
        return result;
    }
};

二叉树 — 层序遍历

层序遍历 I

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

**题目要求：**给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例1：

image-20240924171110192

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

示例 2：

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

示例 3：

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

**思路：**借助队列保存每一层中遍历的元素

解法：

  • C++
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root == NULL) return result;
        que.push(root);
        while(!que.empty()){
            vector<int> vec;   // 保存每一层的节点数据
            int size = que.size();   // 记录每一层节点的数量
            for(int i = 0; i < size; i++){
                TreeNode* cur = que.front();   // 访问队列的头部元素
                que.pop();
                vec.push_back(cur->val);
                if(cur->left)  que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

二叉树的最大深度

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

题目要求：

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

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

**思路：**仍然是使用队列保存每一层的数据，不过在进行层切换时要计数

解法：

  • C++
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int result = 0;
        if(!root) return result;
        que.push(root);
        while(!que.empty()){
            result++;
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left)  que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

二叉树的最小深度

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

题目要求：

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

最小深度是从根节点到最近叶子节点（左右子节点都为 NULL 的节点）的最短路径上的节点数量。

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

示例 1：

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

示例 2：

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

解法：

  • C++
class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int result = 0;
        if(!root) return result;
        que.push(root);
        while(!que.empty()){
            result++;
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left)  que.push(cur->left);
                if(cur->right) que.push(cur->right);
                if(!cur->left && !cur->right) // 当左子节点与右子节点都为空时就代表最小深度
                    return result;
            }
        }
        return result;
    }
};

二叉树 — 翻转二叉树

题目链接：226. 翻转二叉树 - 力扣（LeetCode）

**题目要求：**给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

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

示例 2：

img

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

示例 3：

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

思路：

只要将每一个节点的左右子节点翻转一下，就可以达到整体翻转的效果

使用 前序/后续 对二叉树进行递归遍历，中序（会将某些节点的左右子节点翻转两次）

1、递归函数的参数（TreeNode *），返回值（TreeNode *）

TreeNode* invertTree(TreeNode* cur)

2、终止条件（root == NULL）

if (root == NULL) return NULL;

3、单层递归逻辑（交换传入节点的左右子节点）

swap(root->left, root->right);   // 交换两个变量的值
invertTree(root->left);
invertTree(root->right);

解法：

  • C++（前序遍历 递归）
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return NULL;
        swap(root->left,root->right); // 中
        invertTree(root->left);       // 左
        invertTree(root->right);      // 右
        return root;
    }
};
  • C++（后序遍历 递归）
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return NULL;
        invertTree(root->left);       // 左
        invertTree(root->right);      // 右
        swap(root->left,root->right); // 中
        return root;
    }
};

二叉树 — 对称二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

**题目要求：**给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

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

示例 2：

img

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

思路：

判断是否为对称二叉树，其实就是判断左子树和右子树是否可以相互翻转，真正要比较的是两个树（根节点的左右子树）（比较两个子树的里侧和外侧元素是否相等），所以在递归遍历的过程中，也是要同时遍历两棵树

只能使用后续遍历（左右中）

正因为要遍历两棵树而且要比较内测和外侧节点，所以准确来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中

1、递归函数的参数（TreeNode* left TreeNode* right），返回值（bool）

bool compare(TreeNode* left, TreeNode* right)

2、确定终止条件

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;

3、确定单层递归的逻辑

bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;

解法：

  • C++
class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        if(left == NULL && right == NULL) return true;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right != NULL) return false;
        else if(left->val != right->val) return false; // 这个条件已经比较了每一个节点的值

        bool cmp_left  = compare(left->left, right->right);
        bool cmp_right = compare(left->right, right->left);
        return cmp_left && cmp_right;
    }

    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left, root->right);
    }
};

二叉树 — 二叉树的最大深度

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

**思路：**这里使用递归法，也可以使用层序遍历

使用前序递归求深度，使用后序递归求高度，而根节点的高度就是整个二叉树的深度，所以这道题实际上是使用后续递归求根节点的高度

1、确定递归的参数和返回值

int maxDepth(TreeNode* node)

2、确定终止条件（如果为空节点，就返回0，表示高度为0）

if (node == NULL) return 0;

3、单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度

int leftdepth = getdepth(node->left);       // 左
int rightdepth = getdepth(node->right);     // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;

解法：

  • C++
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int leftdepth  = maxDepth(root->left);       // 左
        int rightdepth = maxDepth(root->right);      // 右
        int depth = 1 + max(leftdepth, rightdepth);  // 中
        return depth;
    }
};

二叉树 — 二叉树的最小深度

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

**思路：**依旧是前序递归遍历求深度，后序递归遍历求高度

这里使用后序遍历求最小深度

最小深度是从根节点到最近叶子节点（左右子节点都为空）的最短路径上的节点数量。

1、确定递归函数的参数和返回值

int minDepth(TreeNode* node)

2、确定终止条件（遇到空节点，返回 0）

if(node == NULL) return 0;

3、确定单层递归的逻辑

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
// 当只有一个子节点时，就顺着这个子节点继续往下查
if(node->left == NULL && node->right != NULL){
	return 1 + rightDepth;
}
if(node->left != NULL && node->right == NULL){
	return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

解法：

  • C++
class Solution {
public:
    int minDepth(TreeNode* root) {
        int result = 0;
        if(root == NULL) return 0;
        int leftDepth  = minDepth(root->left);   // 左
        int rightDepth = minDepth(root->right);  // 右
        if(root->left == NULL && root->right != NULL){
            return rightDepth + 1;
        }
        if(root->left != NULL && root->right == NULL){
            return leftDepth + 1;
        }
        result = 1 + min(leftDepth, rightDepth);
        return result;
    }
};

二叉树 — 完全二叉树的节点数量

题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）

题目要求：

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

img

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

示例 2：

输入：root = []
输出：0

示例 3：

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

**思路：**可以使用层序遍历（只需要在遍历每一层时，记录节点的个数就可以），

使用递归的写法和求二叉树的深度写法类似，顺序依旧是后序（左右中）

1、确定递归的参数和返回值

int getNodesNum(TreeNode* cur)

2、确定终止条件（如果为空姐点的话，就返回 0，表示节点数量为 0）

if(cur == NULL) return 0;

3、确定单层递归的逻辑

int leftNum  = getNodesNum(cur->left);  // 左
int rightNum = getNodesNum(cur->right); // 右
int treeNum  = leftNum + rightNum + 1;  // 中
return treeNum;

解法：

  • C++
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        int leftNum  = countNodes(root->left);
        int rightNum = countNodes(root->right);
        int result = leftNum + rightNum + 1;
        return result;
    }
};

示例 3：*

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

**思路：**可以使用层序遍历（只需要在遍历每一层时，记录节点的个数就可以），

使用递归的写法和求二叉树的深度写法类似，顺序依旧是后序（左右中）

1、确定递归的参数和返回值

int getNodesNum(TreeNode* cur)

2、确定终止条件（如果为空姐点的话，就返回 0，表示节点数量为 0）

if(cur == NULL) return 0;

3、确定单层递归的逻辑

int leftNum  = getNodesNum(cur->left);  // 左
int rightNum = getNodesNum(cur->right); // 右
int treeNum  = leftNum + rightNum + 1;  // 中
return treeNum;

解法：

  • C++
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        int leftNum  = countNodes(root->left);
        int rightNum = countNodes(root->right);
        int result = leftNum + rightNum + 1;
        return result;
    }
};

http://www.niftyadmin.cn/n/5683017.html

相关文章

以太网交换安全：MAC地址表安全

以太网交换安全：MAC地址表安全

一、MAC地址表安全 MAC地址表安全是网络安全中的一个重要方面&#xff0c;它涉及到网络设备的MAC地址表的管理和保护。以下是对MAC地址表安全的详细介绍&#xff1a; &#xff08;1&#xff09;基本概念 定义&#xff1a;MAC地址表是网络设备&#xff08;如交换机&#xff0…
阅读更多...
Pytorch 学习手册

Pytorch 学习手册

零 相关资料 官方网址 官方网址下的API搜索网站 一 定义 深度学习框架是用于设计、训练和部署深度学习模型的软件工具包。这些框架提供了一系列预定义的组件&#xff0c;如神经网络层&#xff08;卷积层、全连接层等&#xff09;、损失函数、优化器以及数据处理工具&#xf…
阅读更多...
MBSE和刚亮相的B-21“突袭者”隐形轰炸机

MBSE和刚亮相的B-21“突袭者”隐形轰炸机

DDD领域驱动设计批评文集>> 《软件方法》强化自测题集>> 《软件方法》各章合集>> 12月2日&#xff0c;B-21“突袭者”隐形轰炸机举行揭幕仪式。 摘译一篇来自制造商Northrop Grumman公司&#xff08;诺斯罗普格鲁曼公司&#xff09;网站上的文章片段。 利…
阅读更多...
Vue.js与Flask/Django后端的协同开发研究

Vue.js与Flask/Django后端的协同开发研究

在现代Web开发中&#xff0c;前后端分离的架构已成为一种趋势。前端框架如Vue.js因其灵活性与易用性受到广泛欢迎&#xff0c;而后端框架如Flask和Django则以其强大的功能和高效的开发效率成为众多项目的首选。本文将探讨如何将Vue.js与Flask/Django后端进行有效结合&#xff0…
阅读更多...
【Wireshark笔记】通过Wireshark检测和分析TCP重传

【Wireshark笔记】通过Wireshark检测和分析TCP重传

通过Wireshark检测和分析TCP重传 在网络通信中&#xff0c;TCP重传&#xff08;TCP Retransmission&#xff09;是一种非常重要的现象&#xff0c;特别是在分析网络性能和故障排查时。重传数据包会影响网络性能&#xff0c;导致延迟增加&#xff0c;甚至引发网络拥塞等问题。为…
阅读更多...
Flink 本地 idea 调试开启 WebUI

Flink 本地 idea 调试开启 WebUI

Flink 本地 idea 调试开启 WebUI Maven 引用相关的包配置端口使用本地带UI环境启动 // maven 导入<!-- flink运行时的webUI --><dependency><groupId>org.apache.flink</groupId><artifactId>flink-runtime-web</artifactId><version…
阅读更多...
报数游戏 - 华为OD统一考试(E卷)

报数游戏 - 华为OD统一考试(E卷)

2024华为OD机试&#xff08;E卷D卷C卷&#xff09;最新题库【超值优惠】Java/Python/C合集 题目描述 100个人围成一圈&#xff0c;每个人有一个编号&#xff0c;编号从1开始到100。他们从1开始依次报数&#xff0c;报到为M的人自动退出圈圈&#xff0c;然后下一个人接着从1开始…
阅读更多...
车辆重识别（利用扩散模型合成有效数据进行行人再识别预训练）论文阅读2024/9/27

车辆重识别（利用扩散模型合成有效数据进行行人再识别预训练）论文阅读2024/9/27

[1]Synthesizing Efficient Data with Diffusion Models for Person Re-Identification Pre-Training 作者&#xff1a;Ke Niu1, Haiyang Yu1, Xuelin Qian2, Teng Fu1, Bin Li1, Xiangyang Xue1*单位&#xff1a;1复旦大学, 2西北工业大学 摘要&#xff1a; 现有的行人重识别…
阅读更多...
最新文章

Copyright @ 2022~2023