每日两题(二叉树三序遍历递归/迭代)

一切递归都能用栈实现对应的迭代版本？

二叉树的迭代遍历

#算法公开课

《代码随想录》算法视频公开课 (opens new window)：

• 写出二叉树的非递归遍历很难么？（前序和后序）(opens new window)
• **写出二叉树的非递归遍历很难么？（中序）) (opens new window)**相信结合视频在看本篇题解，更有助于大家对本题的理解。

看完本篇大家可以使用迭代法，再重新解决如下三道leetcode上的题目：

• 144.二叉树的前序遍历(opens new window)
• 94.二叉树的中序遍历(opens new window)
• 145.二叉树的后序遍历

//
// Created by 徐昊岩 on 2023/11/27.
//
#include "bits/stdc++.h"
using namespace std;
/**
 * 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 traversal(TreeNode* node,vector<int>& res){
        if(node == nullptr) return;
        traversal(node->left,res);
        traversal(node->right,res);
        res.push_back(node->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }
};

class Solution2 {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack1;
        if(root!= nullptr) stack1.emplace(root);
        else return res;
        while (!stack1.empty()){
            TreeNode* p=stack1.top();
            res.push_back(p->val);
            stack1.pop();
            if(p->right!= nullptr) stack1.emplace(p->right);
            if(p->left!= nullptr) stack1.emplace(p->left);
        }
        return res;
    }
};

class Solution3 {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack1;
        if(root!= nullptr) stack1.emplace(root);
        else return res;
        while (!stack1.empty()){
            TreeNode* p=stack1.top();
            if(p->left== nullptr) {
                res.push_back(p->val);
                stack1.pop();
                if(p->right!= nullptr) stack1.emplace(p->right);  
            }
            else {
                stack1.emplace(p->left);
                p->left= nullptr;   //用来标记某个节点已经被访问过了
            }
        }
        return res;
    }
};

/*
 * 再来看后序遍历，先序遍历是 中左右，后续遍历是 左右中，
 * 那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了
 * */
class Solution4 {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};