二叉树的递归遍历

首先需要明确的一点是，前序中序和后序在二叉树的递归遍历中的区别仅在于递归函数中操作的顺序，前序是在遍历一个节点的左右子树前进行操作，中序是在遍历一个节点的左子树后进行操作再遍历右子树，而后序是在遍历完左右子树再进行操作。所以在递归函数中，仅是顺序的差别。前序中序和后序可简化为中左右、左中右和左右中，此外，写递归函数时，需要明确三点：

• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层递归的逻辑

        在对二叉树的递归遍历中，递归函数需要传入树节点TreeNode * cur和vec数组进行操作，无实际返回值，所以函数为void，当递归操作时，若节点为空则返回，对每层递归的逻辑以前序遍历来说，先讲当前节点的val值传入数组vec中，之后遍历左子树，再之后遍历右子树。

代码随想录 (programmercarl.com)二叉树的递归遍历https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF看到递归就晕？带你理解递归的本质！_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1UD4y1Y769/?spm_id_from=333.880.my_history.page.click&vd_source=fc4a6e70e3a87b7ea67c2024e326e7c5

前序遍历递归函数如下所示，

void traversal(TreeNode * cur, vector<int> & vec){//创建前序递归遍历函数
        if(cur == nullptr)//当当前遍历节点为空时，返回
            return;
        vec.push_back(cur->val);//中 将当前遍历节点的val值存入vec数组 *操作
        traversal(cur->left,vec);//遍历左子树
        traversal(cur->right,vec);//遍历右子树
    }

void traversal(TreeNode * cur, vector<int> & vec){//创建中序递归遍历函数
        if(cur == nullptr)//当当前遍历节点为空时，返回
            return;
        traversal(cur->left,vec);//遍历左子树
        vec.push_back(cur->val);//中 将当前遍历节点的val值存入vec数组 *操作
        traversal(cur->right,vec);//遍历右子树
    }

void traversal(TreeNode * cur, vector<int> & vec){//创建后序递归遍历函数
        if(cur == nullptr)//当当前遍历节点为空时，返回
            return;
        traversal(cur->left,vec);//遍历左子树
        traversal(cur->right,vec);//遍历右子树
        vec.push_back(cur->val);//中 将当前遍历节点的val值存入vec数组 *操作
    }

对于主函数体，只需传入节点，在函数体中创建一个ans数组，并传入traversal函数中。

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traversal(root,ans);
        return ans;
    }

递归遍历树节点的时间复杂度和空间复杂度均为O(n)。

二叉树的迭代遍历

前序遍历

        考虑前序递归遍历的过程，若操作为打印，则先将自身val值打印后，对所有左子树打印，然后打印右子树，考虑使用栈来模拟前序遍历的过程（也是用栈来模拟递归的过程），由于栈是先入后出的数据结构，前序遍历结果左子树节点在右子树节点前，所以需先对右子树中节点入栈，再对左子树中节点入栈。然后是大致流程，创建结果数组ans，先判断根节点是否为空，若为空直接返回结果数组，否则将根节点入栈，在一个while循环中实现二叉树的迭代前序遍历，由于栈模拟的递归过程，当栈为空时，也就意味着递归结束，即我们遍历结果结果结束。所以while的循环条件为stack.size()!=0，在循环体内，创建一个指针指向当前节点，将其val值加入ans数组，之后再弹出栈，（第一次循环的pop为根节点，即第一次前序遍历要对根节点进行操作，之后因为我们是对栈是先加入右子树节点后加入左子树节点，所以会先对节点的左子树进行操作后对节点的右子树进行操作，完成前序遍历的过程），之后判断右子树的存在，若存在，将其入栈，判断左子树的存在，存在则将其入栈，这就是循环体内内容。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stack;
        vector<int> ans;
        if(root == nullptr){//当根节点为nullptr，直接返回ans
            return ans;
        }
        stack.push(root);
        while(stack.size()!=0){//栈不为空则循环
            TreeNode*cur = stack.top();//创建cur指针指向栈顶地址
            ans.push_back(cur->val);//将栈顶地址的值存入ans数组
            stack.pop();//出栈
            if(cur->right)//判断左右子树存在的情况，若存在，将其存入栈中，注意顺序，先右后左                
                         //出栈则为先左后右
                stack.push(cur->right);
            if(cur->left)
                stack.push(cur->left);
        }
        return ans;
    }
};

该算法的时间复杂度和空间复杂度均为O(n)。

中序遍历

        在遍历二叉树的节点时，创建遍历指针cur，先遍历左子树，依次将所有左节点全部入栈，当当前节点的左节点为空时，弹出栈中元素给遍历指针cur，并将cur指向的val传入数组中，完成中的操作，令cur = cur->right，并继续进行循环。算法的时间和空间复杂度均为O(n)。

class Solution {
public:
    // 定义一个函数，用于执行中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        // 创建一个空向量 ans，用于存储遍历的结果
        vector<int> ans;
        // 创建一个空栈 st，用于辅助遍历
        stack<TreeNode*> st;
        // 创建一个指针 cur，初始指向根节点
        TreeNode* cur = root;
        // 当 cur 指向的节点不为空或者栈 st 不为空时，进行循环
        while (cur != nullptr || !st.empty()) {
            // 如果 cur 指向的节点不为空，则将其压入栈 st 中，并移动 cur 指针到其左子节点
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            // 如果 cur 指向的节点为空，说明左子节点已经访问完毕，此时从栈 st 中弹出最上面的节点
            else {
                cur = st.top(); // 获取栈顶节点
                st.pop(); // 弹出栈顶节点
                // 将弹出的节点的值添加到 ans 向量中
                ans.push_back(cur->val);
                // 移动 cur 指针到其右子节点
                cur = cur->right;
            }
        }
        // 循环结束后，返回存储遍历结果的 ans 向量
        return ans;
    }
};

后序遍历

        考虑前序遍历和后序遍历的相似之处，调整一下前序遍历中左右节点的入栈顺序，让中左右变为中右左，之后再通过一个reverse即能实现后序遍历。

调整

//前序
if(cur->right)//判断左右子树存在的情况，若存在，将其存入栈中，注意顺序，先右后左                
                         //出栈则为先左后右
stack.push(cur->right);
if(cur->left)
stack.push(cur->left);

//后序
if(cur->left)
stack.push(cur->left);
if(cur->right)
stack.push(cur->right);
            

整体代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stack;
        vector<int> ans;
        if(root == nullptr){//当根节点为nullptr，直接返回ans
            return ans;
        }
        stack.push(root);
        while(stack.size()!=0){//栈不为空则循环
            TreeNode*cur = stack.top();//创建cur指针指向栈顶地址
            ans.push_back(cur->val);//将栈顶地址的值存入ans数组
            stack.pop();//出栈
            if(cur->left)
                stack.push(cur->left);
            if(cur->right)
                stack.push(cur->right);
        }
        reverse(ans.begin(),ans.end());//反转
        return ans;
    }
};

二叉树的统一迭代法

周末再看看

代码随想录 (programmercarl.com)二叉树的统一迭代法https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E6%80%9D%E8%B7%AF