引言上一篇文章《精通二叉树的“独门忍术”——线索二叉树（上）》提到了线索二叉树的改良，并给出了改良后的“中序遍历”“前序遍历”线索二叉树的定义。本文就来谈谈改良后的“前序遍历”的线索二叉树的转换与遍历算法。非递归型算法既然《精通二叉树的“独门忍术”——线索二叉树（上）》中已经给出了“中序遍历”的线索二叉树的转换与遍历算法，那么朴素的想法就是：将“前序遍历”线索二叉树与“中序遍历”线索二叉树进行对比，基于后者来推导出前者的算法。我们先来对比一下“中序遍历”线索二叉树与“前序遍历”线索二叉树的图示：图1“中序遍历”的线索二叉树图2“前序遍历”的线索二叉树对比图2与图1可以看出：“中序遍历”线索二叉
引言二叉树的叶子节点的孩子都是空节点（Null），如果展开显示，如下图：图1原始二叉树二叉树的遍历方法，有“前序遍历”“中序遍历”和“后序遍历”三种。“前序遍历”的规则：先访问当前节点，再访问其左子树，最后访问右子树；访问子树时，按照规则1递归执行。“中序遍历”的规则：先访问左子树，再访问当前节点，最后访问右子树；访问子树时，按照规则1递归执行。“后序遍历”的规则：先访问左子树、再访问右子树，最后访问当前节点；访问子树时，按照规则1递归执行。如果要写出非递归的遍历算法，无论用哪种遍历方法，根据《再不会“降维打击”你就Out了！》《神力加身！动态编程》三篇文章中讲到的知识和技巧，都要借助堆栈来记
引言在上一篇《无死角“盘”它！二分查找树》中提到了：平衡二叉树的目的就是使得平均查找长度最短。那么这里就引出两个问题：什么是平衡二叉树？为什么平衡二叉树的平均查找长度最短？如何将非平衡二叉树调整成平衡二叉树？1.平衡二叉树是什么鬼？满足如下两个条件的二叉树称为“平衡二叉树”：首先它得是二分查找树然后它的左右子树的高度相差不超过1图1平衡二叉树图2非平衡二叉树图1就是一棵平衡二叉树，而图2不是平衡二叉树。在图2中，对于值为9的节点，它的左子树为空，高度为0，右子树高度为3，两者相差3，不满足平衡二叉树定义的第二条规则。2.如何证明平衡二叉树的平均查找长度最短？首先研究一下平衡二叉树与非平衡二叉树
引言《菜鸟也能“种”好二叉树！》一文中提到了：为了方便查找，需要进行分层分类整理。而满足这种目标的数据结构之一就是树。树的叶子节点可以看作是最终要搜寻的目标物；叶子节点以上的每一层，都可以看作是一个大类别、层中的每个节点都可以看作是一个小类别。从上图可以看出，要定位目标物，就需要从最上面的大类依次向下定位目标物所属的小类。定位的效率（时间复杂度）取决于两个因素：非叶子节点的分岔数：分岔数越多，表示大类包含的小类数目也就越多，那么为了定位到底属于哪个小类，比较次数也就越多，从而时间开销也就越大。树的高度（或称为深度）：树越深（高），从根节点（最大类）到叶子节点（目标物）的路径也就越长，也就意味着
引言上一篇文章《菜鸟也能“种”好二叉树！》提到：树是一种分层分类的数据结构，用途是查找和排序。而与查找和排序密切相关的就是求最值（最大值或者最小值）。今天我们就来介绍一个与最值相关的数据结构——二叉堆。尽管网上或者相关的算法书均有对二叉堆算法的介绍，但大部分只停留在how的阶段，并未对一些关键细节进行why的深究。比如：为什么二叉堆的算法都使用数组作为数据结构，而不是链表？为什么要引入二叉堆的调整算法来构造堆？相对于插入法构造堆，为什么更优？为什么不论是调整法还是插入法来构造堆，都是自底向上进行遍历，而不是自顶向下？采用调整法来构造堆，为什么时间复杂度是O(N)？本文旨在填补这个空白，“授人鱼
>引言在本系列第5篇《小白也能玩转数组和链表啦！》中，给出了常用数据结构的全貌图：本文就来讲讲“树”这个数据结构。1.树的本质是什么？本系列第2篇《扫雷还可以这样玩》中提到了算法问题的基本类型——搜索、排序、规划、计算。其中，搜索和排序与生活中朴素的体验息息相关。我们每个人都有如下体验：如果房间乱七八糟，那么找一样东西相当棘手。收拾好房间之后，找东西就容易多了。收拾的过程就是分类、整理的过程。当东西特别多时，往往一个分类还不够——这会导致该分类下的东西太多，找起来仍然很花时间。但是直接简单增加分类的话，当分类增加到一定程度，我们查找分类的时间就会变长。那么怎么解决这个矛盾呢？方法就是给分
本系列的第6篇《再不会“降维打击”你就Out了!》讲述了递归算法的意义、套路，第7篇《神力加身！动态编程》讲述了递归算法的优化，但是在大量的实际项目、工程和大家关心的求职面试中，却会碰到大量消除递归的需求。于是产生了两个问题：1.为什么会有消除递归的需求？2.如果都采用非递归的方式，那么递归算法的独特价值又是什么呢？本文以此为引子，将以你在任何其他算法书中都不会看到的方式，向你揭示递归的高阶技巧，让你彻底掌握递归与非递归的左右互搏之术。今天的小汽车会逐步加速，各位乘客要系好安全带：）1.从哪里来、回到哪里去递归算法在运行的时候，是不断重入同一函数的，既然是重入，就必然要搞清楚一个基本的问题——
引言在上篇文章《再不会"降维打击"你就Out了!》中，提到了递归算法的两个局限性。本文给出解决方案——动态编程。如果说"递归算法"是圣剑的话，那么"动态编程"就是圣衣。两者加持，你便可以爆发究极小宇宙：）递归算法局限性详细分析局限性1（适用性问题）：如果“降维”前的状态集合并不方便用“降维”后的状态集合表示，即状态转移函数不好求，那么该场景使用递归不一定恰当。下面举个例子来说明：有两个集合A和B，A中有n个元素，B中也有n个相同元素，将A中的元素通过映射f，映射到B中的元素，映射f满足：f(f(x))=f(x)，求这样的不同映射有多少
引言刘慈欣的《三体》不仅让中国的硬科幻登上了世界的舞台，更是给广大读者普及了诸如“降维打击”之类的热门概念。“降维打击”之所以给人如此之震撼，在于它以极简的方式，从更高的、全新的技术视角有效解决了当前困局。那么在算法的世界中，是否存在这样的利器呢？答案是肯定的——那就是大名鼎鼎的“递归”。递归思想与传统算法思想的区别传统算法思想是正向演绎逻辑，即：根据已知条件，进行联想、寻找经验库，逐步推导，直到问题解决。而递归思想是逆向归纳逻辑，即：当前问题的求解是否可以由规模小一点的问题求解叠加而来，后者是否可以再由更小一点的问题求解叠加而来……依此类推，直到收敛为一个极简的出口问题的求解。由上可知，递归
引言在本系列第一篇文章[《走下神坛吧！算法》中提到了：算法的作用对象是数据结构数据结构的来源既有硬件维度也有软件维度把项目或者工程看作是大楼的话，那么算法就是建造大楼的具体施工流程和方法，数据结构就是砖块等原材料。常言道：“工欲善其事必先利其器”，既然要研究算法，那么首先就要把它操作的“原材料”一一搞清楚。从本篇文章起，将逐一来讲解各“原材料”的历史来源、使用方法与应用场景。1.数组就是带电梯的小高层数组的形式：<数据类型>数组名[数组长度]形象地讲，数组就是带电梯的小高层。每一个楼层就是数组的一个元素。数组元素的下标，就相当于楼层号然后按电梯楼层号。1.1访问数组元素你按下楼层号
在本系列第1篇《走下神坛吧！算法》中提到了：计算复杂度分为时间复杂度与空间复杂度，第3篇《KO！大O——时间复杂度》详细介绍了时间复杂度，本篇文章来讲讲空间复杂度。空间复杂度和硬件资源开销是一回事情吗？CPU资源开销分析：CPU的资源的设计初衷更多的是用于提升计算性能；对CPU资源的利用，基本原则都是“多多（占用、发挥）益善；加之CPU的资源空间大小与内存、外存和外设比较，非常有限。内存资源开销分析：静态视角：程序要装进内存才能运行动态视角：程序在运行时，动态申请内存外存资源开销分析：静态视角：程序本身，以二进制可执行映像形态，存放在外存上的大小动态视角：程序在运行时，对外存的需求大小（比如，
引言在本系列第1篇《走下神坛吧！算法》中提到了：计算复杂度分为时间复杂度与空间复杂度。本篇文章来讲讲时间复杂度。如何度量时间复杂度时间复杂度由所消耗的时间决定。所消耗的时间由硬件与软件共同决定。在同一硬件条件下，所消耗的时间由软件决定。通常意义上的算法指的是软件算法，所以在谈论时间复杂度时，聚焦软件的时间开销。软件的时间开销=软件各组成部分的时间开销之和。软件最基本的组成部分是语句（或者微观意义下的指令）。注：因为在同一硬件条件、特定的编程语言环境下，基本语句由多少条指令构成、运行的模式都是固定的，所以直接以语句作为基本考察单位即可。整体等于各部分之和对大部分编程语言而言，基本语句无外乎以下两
引言上篇文章介绍了算法的本质和基本概念《算法+数据结构（第01篇）走下神坛吧！算法》，这次我们用实际的问题来做算法实战。假设如下场景：公司新年晚会进行夺宝游戏，奖品是最新款的智能手机、VR游戏机、便携电脑三件套。游戏规则如下：当主持人宣布游戏开始的时候，每位员工的手机上会同时收到两组数字（数组中的每个数字都是正整数且两两不等）和一个目标正整数。员工需要在两组数字中分别取两个数字相加，使得相加的结果与目标正整数最接近。哪位员工先做出结果，那么奖品就归谁。为了使赢率最高，请问应该采用什么样的策略或者方法？显然，这是在对一个特定问题找方法。那么根据上篇文章所讲到的，这就是在求算法。那么如何算法求解呢
引言在互联网、大数据、人工智能火爆的今天，“算法”这个词几乎妇孺皆知，业已成为“高薪”“牛X”的代名词。应不少朋友的邀请，特连载本系列，旨在用最通俗的方式——“”讲人话、无废话、看得懂、用得上“”——将位于神龛之上的算法送进寻常百姓家。本篇作为系列的第一篇，采用“What、Why、How”文章结构，来给大家普及一下算法的基本概念（也纠正一些朋友的错误概念）。WhatisAlgorithm？（算法是个什么鬼）为了不落入俗套，本文不会重复wiki上“算法”的官方定义，而采用启发式结构来阐述算法的本质，试想平时在遇到问题的时候，我们是如何解决的。朴素而广泛的过程方法论如下：重新定义问题，结构化描述根