程序员经验分享-hwhale

2.O(NlogN)的排序算法

2023-05-16

认识O(NlogN)的排序算法

1.剖析递归行为及其时间复杂度的估算

递归过程：递归过程是一个多叉树，计算所有树的结点的过程就是利用栈进行后序遍历，每个结点通过自己的所有子结点给自己汇总信息之后才能继续向上返回，栈空间就是整个树的高度。

例题①用递归方法找一个数组中的最大值。

int process(vector<int> &nums, int L, int R) {
    if (L == R) {
        return nums[L];
    }
    //>>操作是位运算，向右整体移一位，相当于除2，速度比出发运算要快。
    int mid = L + ((R - L) >> 1);
    int leftMax = process(nums, L, mid);
    int rightMax = process(nums, mid + 1, R);
     return max(leftMax, rightMax);
}
int main() {
    vector<int> nums{3, 2, 5, 6, 7, 4};
    int max = process(nums, 0, nums.size() - 1);
    cout << max;
}

对数组[3, 2, 5, 6, 7, 4]调用process(nums, 0, 5)的递归逻辑图如下图，其中p(a,b)表示process(nums, a, b)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yb53sjLX-1645706203709)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1645586313830.png)]

Master公式：
T ( N ) = a × T ( N / b ) + O ( N d ) T(N)= a×T(N/b)+O(N^d) T(N)=a×T(N/b)+O(Nd)
T(N)表示目问题的数据规模是N级别的；T(N/b)表示递归子过程的数据规模是N/b的规模; a表示子过程被调用次数；O(N^d)表示剩下的过程时间复杂度。

满足master公式的递归可以用以下公式求解时间复杂度：

  1. log(b, a) > d -> 复杂度为O(N^log(b, a)})
  2. log(b, a) = d -> 复杂度为O(N^d * logN)
  3. log(b,a) < d -> 复杂度为O(N^d)

满足这样过程的递归可以用master公式求解时间复杂度。

如例题①可以用master公式表示为：T(N) = 2 * T(N/2) + O(1)

2.归并排序

归并排序：

  • 整体就是一个简单的递归，左边排好序、右边排好序、让其整体有序
  • 让其整体有序的过程中用了外排序方法（即merge函数的过程）
  • 利用master公式来求解时间复杂度
void merge(vector<int>& nums, int L, int M, int R) {
    vector<int> help(R - L + 1, 0);
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
    }
    while (p1 <= M) {
        help[i++] = nums[p1++];
    }
    while (p2 <= R) {
        help[i++] = nums[p2++];
    }
    for (i = 0; i < help.size(); ++i) {
        nums[L + i] = help[i];
    }
}

void process(vector<int>& nums, int L, int R) {
    if (L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(nums, L, mid);
    process(nums, mid + 1, R);
    merge(nums, L, mid, R);
}

int main() {
    vector<int> nums{ 3, 2, 5, 6, 7, 4 };
    process(nums, 0, 5);
    for (int i : nums) {
        cout << i << " ";
    }
}
//输出结果为: 2 3 4 5 6 7

归并排序的master公式可以表示为：T(N) = 2T(N / 2) + O(N)。

a = 2, b = 2, d = 1.因此，归并排序的时间复杂度为O(NlogN)，空间复杂度为O(N)。

例题②：小和问题，在一个数组中，每一个数左边比当当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。

例：数组[1, 3, 4, 2, 5]。1左边没有比1小的数；3左边比3小的数位1；4左边比4小的数1、3；2左边比2小的数1；5左边比5小的数为1、3、4；所以小和为1+1+3+1+1+3+4+2=16

//可以用归并求小和
//可以反过来想，1右边有3，4，2，5比1大，产生4个1的小和4；3右边有4、5比3大，产生2个3的小和6；4右边有5比4大，产生一个4的小和4；2的右边有一个5比2大产生一个2的小和。
//归并的过程1和右边4个数都比较过一次，只要左边比右边大就产生一个左边小的数的小和
int merge(vector<int>& nums, int L, int M, int R) {
    vector<int> help(R - L + 1, 0);
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    int res = 0;
    while (p1 <= M && p2 <= R) {
        if (nums[p1] <= nums[p2]) {
            help[i++] = nums[p1];
            res += nums[p1] * (R - p2 + 1);
            ++p1;
        } else {
            help[i++] = nums[p2++];
        }
    }
    while (p1 <= M) {
        help[i++] = nums[p1++];
    }
    while (p2 <= R) {
        help[i++] = nums[p2++];
    }
    for (i = 0; i < help.size(); ++i) {
        nums[L + i] = help[i];
    }
    return res;
}

int process(vector<int>& nums, int L, int R) {
    if (L == R) {
        return 0;
    }
    int mid = L + ((R - L) >> 1);
	return process(nums, L, mid) + process(nums, mid + 1, R) + merge(nums, L, mid, R);
}

3.快速排序

随即快速排序（改进的快速排序）

  • 在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：左侧<划分值、 中间==划分值 、 右侧>划分值
  • 对左侧范围和右侧范围，递归进行
  • 时间复杂度为O(NlogN),空间复杂度为O(logN)。
//荷兰国旗问题,将一个数组以一个数为边界划分三个区域
//处理nums[L,...R]的函数
//默认以num[R]做划分
//返回区域(左边界，有边界)。
vector<int> partition(vector<int> &nums, int L, int R) {
    int less = L - 1; //<区右边界
    int more = R; //>区左边界
    while (L < more) { //L表示当签数的位置 nums[R]->划分值
        if (nums[L] < nums[R]) {
            swap(nums[++less], nums[L++]);
        } else if (nums[L] > nums[R]) {
            swap(nums[--more], nums[L]);
        } else {
            ++L;
        }
    }
    swap(nums[more], nums[R]);
    return vector<int>{less + 1, more};
}

void quickSort(vector<int> &nums, int L, int R) {
    if (L < R) {
        int random = rand() % (R - L + 1) + L;
        swap(nums[random], nums[R]);
        vector<int> p = partition(nums, L, R);
        quickSort(nums, L, p[0] - 1); //<区
        quickSort(nums, p[1] + 1, R); //>区
    }
}

int main() {
    vector<int> nums{ 3, 2, 5, 6, 7, 4 };
    quickSort(nums, 0, nums.size() - 1);
    for (int i : nums) {
        cout << i << " ";
    }
}
//输出结果为: 2 3 4 5 6 7

4.堆排序

4.1大顶堆和小顶堆

堆是具有下列性质的完全二叉树：

  • 每个结点的值都大于等于其左右孩子结点的值，称为大顶堆
  • 每个结点的值都小于等于其左右孩子的值，称为小顶堆。
  • 完全二叉树可以用数组来存储。

如下图的大顶堆

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0oBsR9ma-1645706203710)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1638756626810.png)]

完全二叉树可以用数组来存储，因此完全二叉树的编号就对应数组的下标，二叉树的编号结点具有如下性质，对于任意编号索引大于0的结点，有：

  • 父结点的编号索引为：(k - 1) / 2。
  • 左孩子的编号索引为：2 × k + 1。
  • 右孩子的编号索引为：2 × k + 2。

堆的定义用上面的性质来描述的话，则有：

  • 大根堆：arr[k] > arr[2 × k + 1] && arr[k] > arr[2 × k + 2]
  • 小根堆：arr[k] < arr[2 × k + 1] && arr[2 × k + 1] < arr[2 × k + 2]

4.2heapInsert操作和heapfity操作

①如何把边插入一个数保持变成一个堆？（heapInsert过程）

用户每给一个数，不停向上跟父结点比，如果比父结点大则交换，这样可以保证在插入新的数之后保持形成大根堆。这个过程叫做heapInsert过程。

例：将用户输入给数组的数变成一个大根堆。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kNnQKPjf-1645706203710)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1645690495376.png)]

//heapInsert过程
//某个数现在处于index位置，继续向上移动
void heapInsert(vector<int>& nums, int index) {
    while (nums[index] > nums[(index - 1) / 2]) {
        swap(nums[index], nums[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

②如何知道堆中最大值并把它从堆中去掉？

先用一个临时量记录堆第一个元素，就是堆的最大值。将堆最后一个元素放到第一个元素位置，并减少堆长度即heapSize – 1（把堆最后一个元素放到堆第一个元素位置），此时整体可能不是堆，此时需要调整（进行heapify操作）。从头节点（cur）开始，在它的左孩子和右孩子中选择一个最大值，和头节点比较，如果孩子最大值的值比头节点大则交换两者，直到cur结点没有左孩子和右孩子。

如：弹出堆数组[6 3 5 2 3 4]的最大两个值。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yy5Uw9fC-1645706203710)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1645692811481.png)]

//某个数在index位置，能否往下移动
void heapify(vector<int>& nums, int index, int heapSize) {
    int left = index * 2 + 1; //左孩子下标
    while (left < heapSize) { //下方还有孩子的时候
        //两个孩子中，谁的值大，把下标给largest
        int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
        //父和较大的孩子之间，谁的值大，把下标给largest
        largest = nums[largest] > nums[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(nums[largest], nums[index]);
        index = largest;
        left = index * 2 + 1;
    }
}

③如何将一个已有的数组变成一个大根堆？

heapify解决的是：如果一个二叉树根节点的左右子树都是一个堆，但是加上根节点就可能不是一个堆，用heapify可以将这种二叉树调整成一个堆。

那么对于一个已有数组，我们只要从后往前进行heapify操作即可将这棵树变成大根堆，即将已有数组变成一个大根堆。

for (int i = nums.size() - 1; i >= 0; --i) {
    heapify(nums, i, nums.size());
}

6.3堆排序

堆排序就是利用堆进行排序的方法，升序排序用大顶堆，降序排序用小顶堆（优先级队列其实就是堆结构，默认是小顶堆）。 以升序排序为例，它的基本思想是：

  • 将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根结点。
  • 将它与堆数组的末尾元素进行交换，此时末尾元素就是最大值。
  • 将除了末尾元素的剩余的n - 1个序列重新构造成一个大顶堆，重复上述步骤，便能得到一个有序序列了。
//某个数现在处于index位置，继续向上移动
void heapInsert(vector<int>& nums, int index) {
    while (nums[index] > nums[(index - 1) / 2]) {
        swap(nums[index], nums[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

//某个数在index位置，能否往下移动
void heapify(vector<int>& nums, int index, int heapSize) {
    int left = index * 2 + 1; //左孩子下标
    while (left < heapSize) { //下方还有孩子的时候
        //两个孩子中，谁的值大，把下标给largest
        int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
        //父和较大的孩子之间，谁的值大，把下标给largest
        largest = nums[largest] > nums[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(nums[largest], nums[index]);
        index = largest;
        left = index * 2 + 1;
    }
}

void heapSort(vector<int>& nums) {
    if (nums.size() < 2) {
        return;          
    }
    //相当于把数组变成大根堆
    for (int i = 0; i < nums.size(); ++i) {  //O(N)
        heapInsert(nums, i); //O(logN)
    }
    int heapSize = nums.size();
    swap(nums[0], nums[--heapSize]);
    while (heapSize > 0) { //O(N)
        heapify(nums, 0, heapSize); //O(logN)
        swap(nums[0], nums[--heapSize]); //O(1)
    }
}

int main() {
    vector<int> nums{ 3, 2, 5, 6, 7, 4 };
    heapSort(nums, 0, nums.size() - 1);
    for (int i : nums) {
        cout << i << " ";
    }
}
//输出结果为: 2 3 4 5 6 7
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

NlogN

排序算法

2.O(NlogN)的排序算法 的相关文章

  • 【2023考研】数据结构常考应用典型例题（含真题）

    前言 本文针对 数据结构 博主花了几天时间列出了考研常考的应用题型 讲解详细 方便复习 各类题型所涉及的知识点包括但不限于队列 二叉排序树 平衡二叉树 哈夫曼树及哈夫曼编码 图的存储 最小生成树 关键路径 排序算法等等 标题即为考点 例题出

  • 剑指offer(简单)

    目录 数组中重复的数字 替换空格 从尾到头打印链表 用两个栈实现队列 斐波那契数列 青蛙跳台阶问题 旋转数组的最小数字 二进制中的1的个数 打印从1到最大的n位数 删除链表的节点 调整数组顺序使奇数位于偶数前面 链表中倒数第k个节点 反转链

  • 七大排序算法

    目录 直接插入排序 希尔排序 直接选择排序 堆排序 冒泡排序 快速排序 快速排序优化 非递归实现快速排序 归并排序 非递归的归并排序 排序 所谓排序 就是使一串记录 按照其中的某个或某些关键字的大小 递增或递减的排列起来的操作 常见的排序算

  • 排序算法——比较类排序算法讲解以及c++实现

    首先我先抛一个老哥的博客 我是看着他的博客来学习理解 地址 https www cnblogs com onepixel p 7674659 html 首先说一下排序算法分为2类 一类是比较类排序算法 另一类是非比较类排序 这里主要讲常用的

  • 归并排序（分析与模板）

    归并排序 思路 1 确定分界元素mid left right 2 2 递归分解数组 两两组合组成两个有序数组 3 归并 合二为一 int temp 100010 merge sort int num int l int r if l gt

  • 七大经典排序算法总结【详解】

    排序算法的分类 插入排序 选择排序 交换排序 归并排序 具体分类如图所示 这七种排序算法在我们生活中应用非常广泛 所用的场景各有不同 他的时间复杂度和空间复杂度也是不同的 一 插入排序 初始数据越接近有序 时间效率越高 1 直接插入排序 直

  • C语言库函数——快排函数qsort()

    目录 一 函数原型 二 函数介绍 三 函数使用 常见写法 比较函数 四 函数实例 1 int型数组 2 double型数组 3 char型数组 4 字符串 5 结构体 一级结构 二级结构 一 函数原型 void qsort void bas

  • 计数排序基础思路

    所谓计数排序 也可以称为散列表 也是一种简单的哈希桶 今天 小编带大家来了解计数排序的基本思路 一 基本思路 以升序为例 计数排序通俗来讲 分为三个步骤 首先制作包含所有要排序的数的桶 相同的数制作一个桶即可 以2 3 6 1 4 1 2

  • Java排序算法：选择排序

    Java排序算法 选择排序 选择排序它的主要思想是 在未排序的数组中选择最小的元素 然后将其放置在数组的起始位置 再在剩余的未排序数组中选择最小元素 并将其放置在已排序部分的末尾 重复此过程 直到整个数组排序完成 选择排序的步骤如下 1 从

  • c++用vector先按学生的年级排序，再按学生的分数排序算法

    VectorSort cpp 定义控制台应用程序的入口点 include stdafx h include stdio h include string h include

  • 大数据量的冒泡排序 (计次数)

    题目描述 给定一个包含从0到n 1各一次的数组 若使用冒泡排序将其排为升序 问其中需要进行多少次交换 输入 测试数据有多组 每组由两行组成 第一行包含正整数n n lt 5000 下一行包含从0到n 1的n个整数的序列 输出 对于每组测试数

  • 用 Java 实现的八种常用排序算法

    八种排序算法可以按照如图分类 前置知识 1 算法稳定性 在一个序列中 能保证两个相等的数 经过排序之后 其在序列的前后位置顺序不变 A1 A2 排序前 A1 在 A2 前面 排序后 A1 还在 A2 前面 2 时间复杂度 时间复杂度是用于衡

  • 数据结构--排序之快速排序

    个人主页 你帅你先说 欢迎点赞 关注 收藏 既选择了远方 便只顾风雨兼程 欢迎大家有问题随时私信我 版权 本文由 你帅你先说 原创 CSDN首发 侵权必究 快速排序基本思想及其代码实现 快速排序是Hoare于1962年提出的一种二叉树结构的

  • 九种常见排序的比较和实现

    首先排序算法大的可以分为 关键字比较 非关键字比较 关键字比较 关键字比较就是通过关键字之间的比较和移动 从而使整个序列有序 而关键字比较的算法 又可以像下面这样划分 对于排序算法之间的比较 无异于时间复杂度和空间复杂度 看下面这张表格 由

  • QString转const char*

    QString str hello world 转成const char const char arr str toStdString c str const char arr str toLatin1 constData toUtf8 转

  • 如何学好C语言的数据结构与算法？

    C语言的数据结构与算法 难就难在链表 学会了链表 可能后面就一点都不难了 书籍推荐 数据结构与算法分析 C语言描述版 要深入学习的话可以选择这本书 因为针对链表的讲解是比较详细的 所以可以很快理解链表 跟着书上一点点实现基本操作 增删改查

  • Java 常用的大算法详解

    Java 常用的大算法详解 排序算法是计算机科学中的重要主题之一 Java 提供了许多常用的排序算法 本文将详细介绍其中的几种 并提供相应的源代码实现 冒泡排序 Bubble Sort 冒泡排序是一种简单直观的排序算法 它重复地遍历待排序的

  • 分治-归并算法——LCR 170. 交易逆序对的总数

    文章目录 0 归并排序 1 题目 2 算法原理 3 代码实现 0 归并排序 归并排序是典型的分治 将数组分成若干个子数组 数组两两比较 不是很清楚的 可以查看此篇文章 数据结构 七大排序 这里以力扣 9

  • 分治-归并排序

    文章目录 315 计算右侧小于当前元素的个数 1 题目 2 算法原理 3 代码实现 493 翻转对

  • 八大排序（插入排序 | 选择排序 | 冒泡排序）

    在我们内存中我们一般会有一些没有顺序的数据 我们成为内排序 而今天分享八大排序的是时间复杂度为O N 2 的插入排序 选择排序和教学意义比较强的冒泡排序 插入排序 这是插入排序的动图 通过动图我们也是可以看到我们的插入排序的思想 从当前的位

随机推荐

  • re.sub()用法详解

    源代码 参数及其意义 xff1a def sub pattern repl string count 61 0 flags 61 0 34 34 34 Return the string obtained by replacing the

  • BERT模型的详细介绍

    1 BERT 的基本原理是什么 xff1f BERT 来自 Google 的论文Pre training of Deep Bidirectional Transformers for Language Understanding xff0c

  • 自然语言处理(NLP)之使用TF-IDF模型计算文本相似度

    自然语言处理 NLP 之使用TF IDF模型计算文本相似度 所用数据集 xff1a ChnSentiCorp htl all csv 语料库即存放稀疏向量的列表 要注意的是 xff0c 搜索文本text与被检索的文档共用一个特征词词典 NL

  • C++中关于类重复定义的分析和解决方法

    在C 43 43 中将类以及类中的成员函数的声明放在 h的头文件中 xff0c 而将类中成员函数的定义 xff08 即实现代码 xff09 放在 cpp的源文件中 xff0c 这样我们的程序设计起来更加的模块化 xff0c 但是 xff0c

  • re.search()用法详解

    re search xff1a 匹配整个字符串 xff0c 并返回第一个成功的匹配 如果匹配失败 xff0c 则返回None pattern 匹配的规则 string 要匹配的内容 flags 标志位 这个是可选的 就是可以不写 可以写 比

  • re.findall()用法详解

    re findall xff1a 函数返回包含所有匹配项的列表 返回string中所有与pattern相匹配的全部字串 xff0c 返回形式为数组 示例代码1 xff1a 打印所有的匹配项 import re s 61 34 Long li

  • Linux系统中创建虚拟环境详解

    1 方法一 1 1 安装虚拟环境的命令 xff1a sudo pip install virtualenv sudo pip install virtualenvwrapper 1 2 安装完虚拟环境后 xff0c 如果提示找不到mkvir

  • 使用python将图片改为灰度图或黑白图

    使用python将图片改为灰度图或黑白图有三种方式 xff0c 分别是是使用cv2库和PIL库来实现 xff0c 详细过程如下所示 1 使用cv2库将图片改为灰度图 在使用cv2进行读取原彩色图片时 xff0c 在里面添加一个参数cv2 I

  • 虚拟机中windows镜像下载与安装

    镜像文件下载 xff1a 链接 xff1a https pan baidu com s 1VKWMHHCGRwWXk2GpxyUp0A 提取码 xff1a shlg 注意 xff1a 虚拟机中的镜像和本地电脑系统安装的镜像是一样的 安装教程

  • mongo数据库中字符串型正负数值比较大小

    数据库中数据展示 xff1a 使用python代码实现 xff1a Requires pymongo 3 6 0 43 from pymongo import MongoClient client 61 MongoClient 34 mon

  • flask项目中内部接口调用其他内部接口操作

    1 requests 在 Flask 框架项目中 xff0c 可以通过使用 requests 模块来进行内部接口调用 requests 模块是 Python 中常用的 HTTP 请求库 xff0c 可以用于发送 HTTP 请求和处理响应 示

  • ElasticSearch删除索引中的数据（delete_by_query）

    1 删除两个月以前的数据 在 Elasticsearch 中 xff0c 要删除两个月以前的数据 xff0c 可以通过以下步骤 xff1a 计算当前时间的两个月前的日期 xff0c 可以使用 Python 的 datetime 模块来实现

  • Qt Creator子图绘制

    Qt中在一个窗体文件内画所有图显然是不好维护的 xff0c 我们可以将主窗体拆分为几个子窗体 xff0c 在子窗体中绘制子图 xff0c 这样便于我们去维护我们的代码 1 在工程文件中右键 gt Add New 2 选择Qt 设计师界面 3

  • MessageFilter [target=odom ]: Dropped 100.00% of messages so far.问题解决

    错误提示 WARN 1580994954 426403779 MessageFilter target 61 odom Dropped 100 00 of messages so far Please turn the ros gmappi

  • 电磁循迹智能车基于stm32cubeMX、HAL库—我的第一辆智能车

    我的第一辆智能车 电磁循迹智能车 提示 本文适用于初学 想完成一个基础四轮车练练手者 大佬还请勿喷 不过欢迎提出意见 有纰漏之处我将及时纠正 注 工程代码链接已贴在文末 前言 所用到的硬件平台 stm32f103c8t6 舵机 电机 L29

  • 2022年国赛建模B题思路与程序

    B题 无人机遂行编队飞行中的纯方位无源定位 关键词搜索 xff1a 无人机 xff0c 无源定位 其实这个工作特别多 xff0c 知网一堆 xff0c 如果选这个题一定要想好做的出彩 xff0c 另外网上的场景和本题不是很一样 xff0c

  • 2017全国大学生电子设计竞赛:室内可见光定位装置

  • 基于FreeRTOS下多任务的同时操作

    FreeRTOS移植及多任务的实现 前言 xff1a 一 FreeRTOS移植 xff08 1 xff09 移植准备工作 xff08 2 xff09 FreeRTOS移植到stm32中 xff08 3 xff09 例程验证 二 多任务实现

  • undefined symbol 问题解决记录

    历经一个月 xff0c 昨日完成打印机network部分的编写 c语言 xff0c 编写makefile构建动态库 构建完成后遂进行调用测试 xff0c 出现 xff1a network symbol lookup error usr li

  • 2.O(NlogN)的排序算法

    认识O NlogN 的排序算法 1 剖析递归行为及其时间复杂度的估算 递归过程 xff1a 递归过程是一个多叉树 xff0c 计算所有树的结点的过程就是利用栈进行后序遍历 xff0c 每个结点通过自己的所有子结点给自己汇总信息之后才能继续向

热门标签