算法与数据结构-2

C++软件与嵌入式软件面经解析大全（蒋豆芽的秋招打怪之旅）

本章讲解知识点

• 1.1 算法的时间复杂度和空间复杂度
• 1.2 数组
• 1.3 链表
• 1.4 递归
• 1.5 栈与队列
• 1.6 树与二叉树
• 1.7 二叉堆与最小堆
• 1.8 哈希表
• 1.9 红黑树
• 1.10 Trie（前缀树）
• 1.11 排序算法
• 1.12 查找算法
• 1.13 算法思想——DFS和BFS
• 1.14 算法思想——回溯
• 1.15 算法思想——分治法
• 1.16 算法思想——贪心法
• 1.17 算法思想——动态规划

受众：本教程适合于C/C++已经入门的学生或人士，有一定的编程基础。

本教程适合于互联网、嵌入式软件求职的学生或人士。

故事背景

蒋 豆 芽：小名豆芽，芳龄十八，蜀中人氏。卑微小硕一枚，科研领域苟延残喘，研究的是如何炒好一盘豆芽。与大多数人一样，学习道路永无止境，间歇性踌躇满志，持续性混吃等死。会点编程，对了，是面对对象的那种。不知不觉研二到找工作的时候了，同时还在忙论文，豆芽都秃了，不过豆芽也没头发啊。

隔壁老李：大名老李，蒋豆芽的好朋友，技术高手，代码女神。给了蒋豆芽不少的人生指导意见。

导 师：蒋豆芽的老板，研究的课题是每天对豆芽嘘寒问暖。

故事引入

隔壁老李：豆芽啊，你刷过一段时间的编程题了，感觉什么数据结构非常容易考啊？

蒋 豆 芽：经过我深思熟虑后，我发现，二叉树这个数据结构十分容易考。

隔壁老李：是的，你说得没错，二叉树可以说是面试官最喜欢考的了，数组链表太简单，哈希、红黑树又太难，而二叉树刚刚好，几十行代码就可以实现一个简单的二叉树，同时二叉树又能很好的考察一个考生的功底。

蒋 豆 芽：所以今天就要讲树了，对吧。

1.6 树与二叉树

隔壁老李：没错，树是很重要的数据结构，我们生活中有很多场景，比如，豆芽你家的族谱，是一棵树，企业的上下级关系，是一棵树。我们依据《漫画算法》一书，对树进行一个总结。

好了，豆芽，你来总结一下树的概念吧。

蒋 豆 芽：没问题，一棵树分为根节点、子树、叶子节点，如图：

节点还分为父节点和子节点，如图：

隔壁老李：是的，豆芽，你再来总结二叉树。

蒋 豆 芽：好嘞！二叉树（ binary tree） 是树的一种特殊形式。 二叉， 顾名思义， 这种树的每个节点最多有2个孩子节点。 注意， 这里是最多有2个， 也可能只有1个， 或者没有孩子节点。

二叉树还有两种特殊形式， 一个叫作满二叉树， 另一个叫作完全二叉树。

一个二叉树的所有非叶子节点都存在左右孩子， 并且所有叶子节点都在同一层级上， 那么这个树就是满二叉树。

完全二叉树

对一个有n个节点的二叉树， 按层级顺序编号， 则所有节点的编号为从1到n。 如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同， 则这个二叉树为完全二叉树。

完全二叉树的条件没有满二叉树那么苛刻： 满二叉树要求所有分支都是满的； 而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

隔壁老李：说得很好，我们来实现一棵二叉树吧。

蒋 豆 芽：简单！

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

一棵树由节点构成，节点包含左、右指针分别指向左、右子节点。是不是很简单。

隔壁老李：好了，来说说树的遍历吧。树的遍历就是为了访问树的节点元素。

蒋 豆 芽：树的遍历有四种，前序遍历、中序遍历、后序遍历、层序遍历。

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。简单记就是根-->左-->右。如图：

我们来分析一下：口诀很好记：根-->左-->右。F是根，那就输出F，接下来进入节点F的左边。在左子树中，B是左子树的根，那就输出B；那又进入左边，左边只有A最后一个节点了，输出A。然后返回节点B，根-->左都输出了，就轮到右了，进入节点B的右边，节点C、D、E构成一棵子树，节点D是根，按照根-->左-->右的口诀，按顺序输出D、C、E。

接下来都是按照这个思路，直到遍历完所有节点。在遍历的过程中，遇到空节点就返回上一层节点。

我们再通过动图直观感受下：

我们给出代码：

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;
    }
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。简单记就是左-->根-->右。如图：

我们来分析一下：口诀很好记：左-->根-->右。F是根，要找到左节点，接下来进入节点F的左边。在左子树中，B是左子树的根，还不够，我们要一路向左；那又进入左边，左边只有A最后一个节点了，终于找到了，输出A。然后返回节点B，B是根，输出B。左-->根都输出了，就轮到右了，进入节点B的右边，节点C、D、E构成一棵子树，节点D是根，按照左-->根-->右的口诀，按顺序输出C、D、E。

接下来都是按照这个思路，直到遍历完所有节点。在遍历的过程中，遇到空节点就返回上一层节点。

我们再通过动图直观感受下：

我们给出代码：

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> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。简单记就是左-->右-->根。如图：

我们来分析一下：口诀很好记：左-->右-->根。同样的思路，我们就不再赘述了。在遍历的过程中，遇到空节点就返回上一层节点。

我们再通过动图直观感受下：

我们给出代码：

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> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

其实利用递归遍历树很简单，我们还可以利用栈来实现树的遍历。如下，我们用栈来实现前序遍历。

我们来分析一下：前序遍历，口诀很好记：根-->左-->右。所以根先入栈，从节点F开始，F为根，入栈并输出F。进入节点F的左边，在左子树中，节点B为根节点，入栈并输出B，然后向左。A节点与两个空节点构成一棵子树，A为根，入栈并输出A。左就访问完了，这时A就要出栈。

根-->左访问完了，开始访问右，怎么到达右边呢？别忘了，我们栈顶保存了B节点，通过获取栈顶元素，也就可以访问节点B的右边了，所以此时获取B节点后，让B出栈。

D、C、E构成右边的子树，接下来就是重复以上的步骤了。直到栈为空，整棵树也就完成输出了。

我们给出代码实现：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) { // 前序遍历，口诀很好记：根-->左-->右。
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val); // 前序遍历，先访问根
                stk.emplace(node);      
                node = node->left;           // 接下来进入左子树
            }
            if (!stk.empty()){
                node = stk.top();
                stk.pop();
                node = node->right;          // 接下来进入右子树
            }
        }
        return res;
    }
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

好了，介绍最后一种层序遍历。如图

我们来分析一下：层序遍历，就是一层一层按顺序访问节点。所以根先入队列，从节点F开始，F为根，入队列并输出F，输出完就要让F出队列了。然后就判断F节点是否有左右子节点，如果有，就让左右子节点入队列。

接下来就是依次取队列前面的元素了，取出B节点，让B出队并输出B，然后判断B节点是否有左右子节点，如果有，就让左右子节点入队列。

又取出G节点，让G出队并输出G，然后判断G节点是否有左右子节点，如果有，就让左右子节点入队列。

可以注意到第7和第8行，因为节点A没有子节点，所以此时队列的状态不变。

重复以上步骤，直到队列没有元素可取了，此时整棵树也输出完毕了。

我们再通过动图直观感受下：

我们给出代码：层序需要利用队列来实现。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == NULL) return {};
        queue<TreeNode*> que;            // 创建队列
        que.push(root);                  // 根节点先入队
        vector<vector<int>> res;
        while (!que.empty()){
            vector<int> vec;
            int len = que.size();
            for (int i=0; i<len; i++){
                TreeNode* node = que.front();
                vec.push_back(node->val);                       // 访问根节点
                que.pop();                                      // 根节点出队列
                if (node->left != NULL) que.push(node->left);   // 左节点入队
                if