算法学习随笔 6

   本章记录一些有关栈和队列的一些较为经典或者自己第一次做印象比较深刻的算法以及题型，包含自己作为初学者第一次碰到题目时想到的思路以及网上其他更优秀的思路，本章持续更新中......

目录

一、二叉树遍历

No 144. 二叉树的前序遍历(简单）

No ​​​​​94. 二叉树的中序遍历(简单)

No 102. 二叉树的层序遍历 (中等)

No 429. N 叉树的层序遍历(中等）

---

一、二叉树遍历

No 144. 二叉树的前序遍历(简单）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

题目描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

思路：通过这个题对递归遍历的前、中、后序遍历和迭代遍历的前序、后序遍历方式做一个总结。

为什么这里不总结迭代方式的中序遍历呢？因为迭代法的中序遍历和前序、后序的代码逻辑有所不同。

        递归法：使用递归的三个最重要的部分就是1、确定递归函数的参数和返回值；2、确认递归函数的终止条件；3、确认递归函数的逻辑。

        1、确定递归函数的参数和返回值：由于题目要求返回节点值，所以要用一个容器来保存节点值，同时还要有一个节点参数。

        2、确定递归函数的终止条件：如果当前拿到的节点为NULL，则递归结束

        3、确定递归函数的逻辑：前序遍历的顺序是中左右，所以要先处理中加节点的值，然后再递归处理左右节点。

如果是中序和后序，只需要调换代码顺序即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归法
    void doPreorderTraversal(TreeNode* cur,vector& res){
        if(cur==NULL){
            return;
        }
        //前序遍历：中左右，其他顺序只需要调换代码位置即可
        res.push_back(cur->val);
        doPreorderTraversal(cur->left,res);
        doPreorderTraversal(cur->right,res);
    }
    //递归法
    vector preorderTraversal(TreeNode* root) {
        vector res;
        doPreorderTraversal(root,res);
        return res;
    }
};

迭代法：迭代法相比于递归法要复杂一点，需要用一个栈来实现。

利用栈的后进先出特点，先把跟节点入栈，然后只要栈不为空就进入循环，在循环中，拿到栈顶节点并出栈，然后将栈顶节点的值放到结果中，之后先将右节点入栈，再将左节点入栈。

因为栈是后进先出，所以要先把右节点入栈，这样出栈的时候右节点就是后入栈的，这是前序遍历的思路。

对于后序遍历，要实现左右中的遍历顺序，其实可以把前序遍历稍加修改，编程中右左的顺序遍历，最后再把结果翻转一下，不就是左右中的遍历顺序了。

后序遍历的迭代和前序遍历的迭代代码风格和逻辑上有很大的相似之处，主要原因是要处理的节点就是每次拿到的节点，都是中间节点。

中序则不同，要处理的节点和拿到的节点不是同一个，所以递归的逻辑有所不同。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //迭代法
    vector preorderTraversal(TreeNode* root) {
        stack treeStack;
        vector res;
        if(root==NULL){
            return res;
        }
        //先把树根入栈
        treeStack.push(root);
        while(!treeStack.empty()){
            //遍历栈中的节点，拿到以后就出栈
            TreeNode* cur=treeStack.top();
            treeStack.pop();
            //把这个节点的数值放入结果中
            res.push_back(cur->val);
            //先把右节点入栈，才能保证出栈的时候先拿到左节点
            if(cur->right!=NULL){
                treeStack.push(cur->right);
            }
            if(cur->left!=NULL){
                treeStack.push(cur->left);
            }
        }
        return res;
    }
};

No ​​​​​94. 二叉树的中序遍历(简单)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

题目描述：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

思路：利用这一题来总结一下中序遍历的迭代法和统一风格的前中后序遍历的迭代方式代码。

中序遍历迭代法：中序遍历的迭代法需要特殊处理一下，因为要处理的节点和每次拿到的节点不一样。

所以如果拿到的节点不为NULL，那么就把该节点入栈，然后移动到该节点的左节点(注意是移动，不是入栈)，进行下一轮循环。

如果当前拿到的节点为NULL，表示此时栈顶的节点就是这课二叉树最左下方的节点了，此时拿到该节点并出栈，然后把该节点的值添加到结果中，最后移动到该节点的右节点，之后开始下一轮循环。

文字描述可能有点难理解，最好可以画个图感受下，可以加深理解。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector inorderTraversal(TreeNode* root) {
        // //递归法
        // vector res;
        // doInorderTraversal(root,res);
        // return res;

        //迭代法
        stack treeStack;
        vector res;
        TreeNode* cur=root;
        while(!treeStack.empty()||cur!=NULL){
            //有左节点
            if(cur!=NULL){
                treeStack.push(cur);
                cur=cur->left;
            }
            //没有左节点了
            else{
                //此时栈顶是没有左节点的那个节点，也就是当前的中间节点
                cur=treeStack.top();
                //一般是拿到就出栈，防止遗漏
                treeStack.pop();
                //把中间这个节点添加到结果中
                res.push_back(cur->val);
                //访问这个节点的右节点
                cur=cur->right;
            }
        }
        return res;
    }
};

统一风格的三种遍历方式的迭代法：一般的迭代法在在三种遍历方式中代码风格不统一，因此如果有一种统一的代码风格和相似的逻辑，只需要想递归那样变换代码顺序就会方便不少。

要想做到这一点，就需要对中间节点进行一个特殊处理，先进行记录，最后在进行统一的处理。

我们可以在每次中间节点入栈后在入栈一个NULL，后续只有当遍历到NULL的时候，再处理节点的值。

具体方法是，在进入循环之前先把根节点入栈，循环结束条件是栈为空。

在循环中，从栈顶拿到一个节点并d出，只要当前节点不为空，我们就入栈，入栈的具体方式要看是什么遍历方式，以中序遍历为例，先入栈右节点，再入栈中间节点，最后入栈左节点，注意要在中间节点入栈之后紧跟一个NULL。

如果当前拿到的节点是NULL，那么此时栈顶元素就是要处理的中间节点(因为在循环开始时，拿到栈顶的NULL后就d出了)。

此时只需要拿到栈顶节点并d出，对节点的值进行记录即可。

这样就做到了代码的风格统一，对于不同的遍历顺序，只需要改变入栈的代码顺序即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //统一写法：左中右
    vector inorderTraversal(TreeNode* root) {
        vector res;
        stack treeStack;
        //root不为空，先入栈
        if(root!=NULL){
            treeStack.push(root);
        }
        //开始遍历，左中右的时候要先入栈右节点，其他遍历方式调换顺序即可
        while(!treeStack.empty()){
            //拿到第一个节点就出栈，防止重复
            TreeNode* cur=treeStack.top();
            treeStack.pop();
            //遇到非空节点都要判断左中右节点并执行对应入栈逻辑
            if(cur!=NULL){
                //右节点入栈
                if(cur->right!=NULL){
                    treeStack.push(cur->right);
                }
                //中间节点，加入一个NULL，表示这是待处理的节点
                treeStack.push(cur);
                treeStack.push(NULL);
                //左节点入栈
                if(cur->left!=NULL){
                    treeStack.push(cur->left);
                }
            }
            //遇到了空节点，表示下一个节点是要处理的节点
            else{
                //拿到栈顶元素，此时已经不是NULL了，是要处理的节点
                cur=treeStack.top();
                treeStack.pop();
                //把value放入结果中
                res.push_back(cur->val);
            }  
        }
        return res;
    }
};

No 102. 二叉树的层序遍历 (中等)

来源：力扣（LeetCode）
链接：​https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题目描述：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。

（即逐层地，从左到右访问所有节点）。

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

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

​思路：这一题来总结一下层级遍历，也就是广度优先搜索。

层先遍历就是按照一层一层的顺序来遍历，结合示例应该可以很容易理解。

要做到层先遍历，一个关键点是要拿到每一层的节点数量，这个节点数量可以通过队列的大小来获取。

层先遍历需要使用到队列，而不是栈。

队列先进先出的特点可以很好的把节点的顺序记录下来。

具体方法是：首先将根节点入队，然后进入循环，循环的结束条件是队列为空。

在循环中，我们要做的是首先是得到此时队列的大小，因为每一轮循环开始之前的队列的大小就是当前层的节点数量。

拿到节点数量之后我们就可以在一个 for 循环中对这一层的节点进行 *** 作了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        queue treeQueue;
        vector> res;
        if(root!=NULL){
            treeQueue.push(root);
        }
        while(!treeQueue.empty()){
            vector res_eachLine;
            //每一层的大小，因为返回的是二维的vector，所以要在循环内定义一个一维的vector存档当前层的结果
            int lineSize=treeQueue.size();
            for(int i=0;ival);
                if(cur->left!=NULL){
                    treeQueue.push(cur->left);
                }
                if(cur->right!=NULL){
                    treeQueue.push(cur->right);
                }
            }
            res.push_back(res_eachLine);
        }
        return res;
    }
};

No 429. N 叉树的层序遍历(中等）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

题目描述：

给定一个 N 叉树，返回其节点值的层序遍历。

（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

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

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

思路：本题其实是层先遍历的扩展，把子节点从2个扩展成为了n个。

做法和思路是一样的，唯一不同的地方在于对入栈的处理。

二叉树中子节点是两个，我们可以用两行代码来入队，N叉树其实也是一样的道理，只不过入栈的时候需要用 x 行代码来入队，这个 x 就是当前节点的子节点数量。

所以相比于二叉树，我们要再多获取一个值，就是当前节点的子节点数量，根据代注释中给出的定义，我们知道子节点是用vector保存的，可以用一个size()来获取数量，之后用for循环入栈即可。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector> levelOrder(Node* root) {
        vector> res;
        queue treeQueue;
        if(root!=NULL){
            treeQueue.push(root);
        }
        //层先遍历
        while(!treeQueue.empty()){
            //获取层的大小
            int lineSize=treeQueue.size();
            //用于存放每一层的数据
            vector lineTemp;
            //每一层遍历
            for(int i=0;ival);
                //获取孩子数量，把所有的孩子节点加入队列,cur->children是一个vector
                int childrenNum=cur->children.size();
                //把不为空的孩子节点加入队列
                for(int j=0;jchildren[j]!=NULL){
                        treeQueue.push(cur->children[j]);
                    }
                }
            }
            //把每一层的写入到结果队列中
            res.push_back(lineTemp);
        }
        return res;
    }
};