当前位置：首页 > article >正文

11.递归遍历、迭代遍历、统一迭代、层序遍历

article 2025/2/10 5:44:09

递归算法

三要素

参数和返回值
终止条件
单层返回逻辑

例题

leetcode：

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

迭代遍历

递归的本质还是利用栈实现的，所以我们可以配合栈来实现迭代遍历

前序遍历

先压入root；

root出栈时，压入右左节点，然后重复该过程直到栈空。

class Solution {
public:
   
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;

        stack<TreeNode*> Mysta;
        if(root)Mysta.push(root);
        while(!Mysta.empty()){
            TreeNode* cur=Mysta.top();
            Mysta.pop();
            if(cur->right)Mysta.push(cur->right);
            if(cur->left)Mysta.push(cur->left);
            res.push_back(cur->val);
        }
        return res;
    }
    
};

中序遍历

中序遍历不能直接改编前序遍历；

把左边一支全部压栈；

然后吐出栈顶为cur，处理完后，将当cur的右节点以及左边的一支压入

class Solution {
public:
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> Mysta;
        TreeNode* cur=root;
        while(cur){
            Mysta.push(cur);
            cur=cur->left;            
        }
        while(!Mysta.empty()){
            cur=Mysta.top();
            Mysta.pop();
            if(cur->right){
                TreeNode* tmp=cur->right;
                
                while(tmp){
                    Mysta.push(tmp);
                    tmp=tmp->left;
                }
            }
            res.push_back(cur->val);
        }
        return res;
    }
};

后序遍历

后序遍历可以通过镜像的先序遍历，然后反转整个结果得到。

class Solution {
public:
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        if(root)
        stack.push(root);
        while(!stack.empty()){
            TreeNode* cur=stack.top();
            stack.pop();
            res.push_back(cur->val);
            if(cur->left)stack.push(cur->left);
            if(cur->right)stack.push(cur->right);
            
        }
        reverse(res.begin(),res.end());
        return res;
    }
};