笔试面试题——二叉树进阶（三）

发布时间：2024年01月22日

在这里插入图片描述


📘北尘_：个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》
??走在路上，不忘来时的初心

文章目录

一、二叉树的前序非递归遍历

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解

在这里插入图片描述

3、代码实现

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

        TreeNode* cur=root;
        while(cur || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                v.push_back(cur->val);
                cur=cur->left;
            }
            TreeNode* top=s.top();
            s.pop();
            cur=top->right;
        } 
        return v;
    }
    
};

二、二叉树的中序非递归遍历

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解

在这里插入图片描述

3、代码实现

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

三、二叉树的后序非递归遍历

1、题目讲解

在这里插入图片描述

2、思路讲解

在这里插入图片描述

3、代码实现

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur=root,*prev=nullptr;
        while(cur || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            TreeNode* top=s.top();
            if(top->right==nullptr || top->right==prev)
            {
                s.pop();
                v.push_back(top->val);
                prev=top;
            }
            else
            {
                cur=top->right;
            }
        }
        return v;
    }
};
文章来源:https://blog.csdn.net/2301_78995005/article/details/135758810
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章