Junyuan's Homepage

150. 递归遍历

题目链接：click here
文章讲解：click here
题目描述：递归法实现二叉树的前中后序遍历
思路：
关键是确定好递归函数的写法：
传参与返回值、收敛条件、单次递归的逻辑
以前序遍历为例：上述三个问题的回答分别是：
传参与返回值：

当前节点、结果res；返回void
1
void traversal(TreeNode* cur, vector<int>& vec)
收敛条件：当前节点为空，直接return
1
if (!cur) return;
单次递归的逻辑：按前序，即，根左右的顺序，遍历节点，结果存入res中。
其中对左右子树的结果，需要递归调用该函数。
1
2
3
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右

代码：

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) 空间复杂度，栈的空间消耗

对应的中序、后序遍历只要微调递归内部的逻辑即可：

中序：左根右

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

后序：左右根

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

239. 统一迭代

题目链接：click here
文章讲解：click here
题目描述：使用迭代法完成二叉树的前中后序遍历
思路：
关键是迭代法与递归的区别
迭代法需要手动模拟递归函数的调用过程，那么就使用栈。
这里我重点关注统一迭代法，它能让前中后序代码的逻辑调整和刚刚递归法一样简单。

具体的是采用标记法，区分 访问、处理 两步

访问：拿到当前节点，对当前节点及其左右子节点，按照所需顺序压入栈内，
比如中序：需要左中右的顺序输出，那么就按照右中左的顺序入栈
注意，这里需要先将栈顶的“当前节点”pop掉，防止后续重复处理，或者说，也是为了访问内部压入栈的逻辑简洁

处理：通过特殊标记，表面迭代过程中标记后一位就是需要处理的，也就是值需要被打印的。
先pop掉特殊标记，拿到当前节点的值并打印，pop当前节点。

中序遍历代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            // 访问环节
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } 
            // 处理环节
            else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

前序、后序只需要修改访问环节的逻辑如下

前序：

if (node != NULL) {
    st.pop();
    if (node->right) st.push(node->right);  // 右
    if (node->left) st.push(node->left);    // 左
    st.push(node);                          // 中
    st.push(NULL);
}

后序：

if (node != NULL) {
    st.pop();
    st.push(node);                          // 中
    st.push(NULL);

    if (node->right) st.push(node->right);  // 右
    if (node->left) st.push(node->left);    // 左

}

347. 层序遍历

题目链接：click here
文章讲解：click here
题目描述：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
思路：
这里我觉得迭代法反而更轻松易懂
拿到一个节点，就把他的左右子节点放入队列中，然后将他的值输出
如此循环，直到队列为空
细节在于，如何把控遍历队列，使得刚好遍历完这一层的所有节点
在遍历队列开始前，就先获取队列的长度，这就是在处理上一层节点时，压入队列的所有的当前层节点的长度了。
由于遍历本层队列过程中，可能会在队列后方压入下一层的节点，所以这里个数要提前获取，防止过程中被修改了。

迭代代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

递归法代码：
确定递归函数传参及返回值：传入当前节点、结果、深度[控制本次递归函数内部是在第几个vector里写数据]
递归终止条件：当前节点为null
递归内部逻辑：根据深度，在当前对应的vector内写下当前节点的值，递归调用左右子节点，注意深度加1。

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：二叉树的前中后序遍历，递归、迭代统一写法；二叉树的层序遍历，递归，迭代写法

递归写法注意提前想清楚：函数的传参与返回值、递归终止条件、递归内部逻辑
耗时：2h

Junyuan Lu(陆俊元)

代码随想录算法训练营第十三天 | 递归遍历、统一迭代、层序遍历

150. 递归遍历

239. 统一迭代

347. 层序遍历

今日收获