[数据结构与算法] 手撕二叉树遍历（前序 + 中序 + 后序递归 + 非递归代码实现 + 例题）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 手撕二叉树遍历（前序 + 中序 + 后序递归 + 非递归代码实现 + 例题） -> 正文阅读

[数据结构与算法]手撕二叉树遍历（前序 + 中序 + 后序递归 + 非递归代码实现 + 例题）

文章目录

前引

刚刚才写完了手撕最小堆的博客就想了是不是也得写一下二叉树遍历呢哈哈因为前段时间才写过而且那个时候理解花了很多时间所以现在手撕了三个遍历大概花了5分钟左右力扣三道题前中后序遍历也就一次性全部AC啦把这篇写了我就去吃晚饭了惹那进入下面的题目吧

手撕数据结构总结博客链接

手撕数据结构（最小堆 + 二叉树前中后非递归遍历 + 快排归并排序 + KMP匹配算法 + AVL + 红黑树）

二叉树遍历介绍

二叉树真的是经典的不能再经典对于其三个非递归的遍历必须熟练熟练的掌握！面试肯定是非常常考的肯定不会考你递归的那不然也太弱智了哈哈

二叉树遍历首先需要先搞清楚什么是前序什么是中序什么是后序我们后面都会用到这张图分别再将这里就先不说了
遍历当然不仅仅是需要用在二叉搜索树任意的树都可以遍历但是对于二叉搜索树的前中后序遍历的话就有一些其他的性质了这个后面再说

1、二叉树前序遍历

在讲代码实现前我们把上面的前序的结果给出来

我们可以理解我们最偏向于先输出值然后其次是向左节点移动最后向右节点移动每当移动后我们又会按照这个顺序进行动作

1、二叉树前序遍历代码（递归）

作为最经典的递归实现递归代码如下

class Solution {
public:
    void preorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        ret.emplace_back(root->val);
        preorder_visit(root->left,ret);
        preorder_visit(root->right,ret);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        preorder_visit(root,ret);
        return ret;
    }
};

2、二叉树前序遍历代码（非递归）

感觉我讲怎么非递归也不好讲
我是以一种抽象的具象化来写的代码
我认为就是前序的话我们每当访问到一个节点时即刻放入数组中
而遍历到最左边的时候看是否有右边的结点如果有再进入循环没有的话也无所谓当前指针等于nullptr 进入下一轮循环即可

大家还是结合代码理解一下吧

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* ptr = root; 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr);        //放入指针
                ret.emplace_back(ptr->val);//即刻放入
                ptr = ptr->left;		 
            }
            
            ptr = stack.top()->right; //访问顶部的右边指针
            stack.pop();			  //已经用过了 则直接pop
        }
        return ret;
    }
};

2、二叉树中序遍历

一样的为了大家方便理解还是花点时间我自己再做一下中序遍历的结果

中序遍历的话我们还是直接看下面的代码吧大家跟着这个图一起理解

1、二叉树中序遍历代码（递归）

直接给代码了

class Solution {
public:
    void inorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        inorder_visit(root->left,ret);
        ret.emplace_back(root->val);
        inorder_visit(root->right,ret);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;

        inorder_visit(root,ret);
        return ret;
    }
};

2、二叉树中序遍历代码（非递归）

这部分我还是花点时间来写吧
我的理解是我们还是跟着递归代码来写
首先不再是遇到节点就push数字了而是从stack顺着递归的顺序来push 如果是从stack里面出来的再push 然后ptr还是一样的从stack.top()->right没变变得只是 push数字的顺序

代码实现如下

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* ptr = root; 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr); //储存指针
                ptr = ptr->left;  
            }
            
            ptr = stack.top();   //倒出来指针
            stack.pop();		 //用过了
            ret.emplace_back(ptr->val); // 把值再放进去 按照递归顺序
            ptr = ptr->right;			// 看看右边指针
        }
        return ret;
    }
};

3、二叉树后序遍历

老样子放一下后序遍历结果图

1、二叉树后序遍历代码（递归）

直接放代码了

class Solution {
public:
    void postorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        postorder_visit(root->left,ret);
        postorder_visit(root->right,ret);
        ret.emplace_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postorder_visit(root,ret);

        return ret;
    }
};

2、二叉树后序遍历代码（非递归）

后序相对前序与中序就不一样了一点也要难了一点但是只是有那么一点不同因为我们需要直到是否当前节点已经被用尽了
对我是这样理解的用尽了必须要求右边节点在当前节点前被push进入数组如果前一个右边指针不是pre指针那么说明右边要不就是nullptr 如果是空指针则我们可以直接推入数组了因为说明当前这个指针已经是最后一个了
我理解的代码也就是这样写的写出来就是如下不是很好理解希望大家多花点时间理解以下代码

那最后一个就直接放代码了

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* ptr = root,*pre = nullptr; \\pre指针 记录前一个被推入数组 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr);
                ptr = ptr->left;
            }
            
            ptr = stack.top();
            if(!ptr->right || ptr->right == pre) //如果右边指针为空 或者右边已经被推入了 则可以直接推入
            {
                ret.emplace_back(ptr->val);
                pre = ptr;
                stack.pop();
                ptr = nullptr;
            }
            else    ptr = ptr->right;
        }
        return ret;
    }
};