前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树的前 中 后序的非递归实现(图文详解)

二叉树的前 中 后序的非递归实现(图文详解)

作者头像
初阶牛
发布2023-10-22 16:26:57
3920
发布2023-10-22 16:26:57
举报
文章被收录于专栏:C语言基础C语言基础

前言

为什么要掌握非递归呢? 递归实现前中后序遍历十分轻松,二非递归就复杂许多了.

主要是递归有以下几个缺陷:

  1. 内存消耗:递归算法由于会在堆栈中不停地压入和弹出函数调用记录,因此会占用大量的内存,如果递归的次数过多,可能会导致栈溢出。
  2. 效率低下:递归算法的效率低下,因为每次递归都需要重新压入调用记录和恢复上一次的状态,这些操作都会增加额外的开销,导致递归算法效率低下,特别是在处理大量数据时会更为明显。
  3. 可读性较差:递归算法的代码一般会比较复杂,理解和维护难度较大,而且递归算法往往涉及到栈的使用,在理解和分析时需要一定的数学基础。

总结:主要害怕栈溢出,其次,可以增加一点点效率.

一、非递归实现"前序遍历"

题目链接:传送门

题目要求: 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

补充知识: 二叉树的前序遍历,又称为先序遍历,是指先访问节点本身,然后按照先左后右的顺序遍历其左右子树。具体步骤如下:

  1. 访问根节点。
  2. 遍历左子树,即对左子节点进行前序遍历。
  3. 遍历右子树,即对右子节点进行前序遍历。

方法一、思路分析:

在这里插入图片描述
在这里插入图片描述
  1. 根节点入栈.
  2. 栈顶元素入存入vector,根节点出栈.
  3. 右孩子入栈
  4. 左孩子入栈

因为我们要求: 先访问左孩子,再访问右孩子. 而栈是后进先出的结构,所以: 右孩子先入栈,左孩子后入栈.

步骤示例图:

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

(图片为博主:"初阶牛"原创,未经允许,不得复制)

结果:

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

🍔非递归代码实现1:

代码语言:javascript
复制
 class Solution {
 public:
     vector<int> preorderTraversal(TreeNode* root) {
         stack<TreeNode*> s1;
         vector<int> v1;
         s1.push(root);//根节点先入栈

         while (!s1.empty()) {				//当栈为空时,结束
            TreeNode* top = s1.top();
            if(top==nullptr)break;
            v1.push_back(top->val);			//出栈前,先将栈顶元素存入vector

             //栈顶元素出栈
            s1.pop();
             //栈顶元素的右左子树入栈
            if (top->right)
                 s1.push(top->right);
            if (top->left)
                 s1.push(top->left);
         }
         return v1;
     }
 };

方法二、思路分析

在这里插入图片描述
在这里插入图片描述
  1. 左路节点一边存入vector,一边入栈.
  2. 栈顶元素出栈,如果栈顶元素有右子树,则将右子树转化为子问题,和步骤1一样.

注意循环的结束条件.

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

(图片为博主:"初阶牛"原创,未经允许,不得复制)

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

(图片为博主:"初阶牛"原创,未经允许,不得复制)

🍉非递归实现2:

代码语言:javascript
复制
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v1;
        stack<TreeNode*> s1;
        TreeNode* cur=root;
        while(cur || !s1.empty()){
            //将左路节点全部存入栈
            while(cur){
                v1.push_back(cur->val);
                s1.push(cur);
                cur=cur->left;
            }
            //栈顶元素出栈
            TreeNode*top=s1.top();
            s1.pop();
			//如果栈顶元素的右子树存在,则转化为子问题解决.
            if(top->right)
                cur=top->right;	//关键语句,通过让cur等于栈顶元素的右子树.
        }
        return v1;
    }
};

二、非递归实现"中序遍历"

题目链接:传送门

题目描述: 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

补充知识: 二叉树的中序遍历指的是按照从小到大的顺序,依次访问二叉树中的所有节点。即先访问左子树,再访问根节点,最后访问右子树。

中序遍历算法如下:

  1. 如果当前节点的左子树非空,则递归遍历左子树。
  2. 访问当前节点。
  3. 如果当前节点的右子树非空,则递归遍历右子树。
在这里插入图片描述
在这里插入图片描述

思路分析:

有了前面的前序遍历的思想,对于中序遍历,需要注意的是存入容器(这里是vector)的时机.

  1. 左路节点依次入栈.(与前序对比:此时入栈并没有入容器.)
  2. 栈顶元素入容器,栈顶元素出栈,栈顶元素的右子树子问题解决.
在这里插入图片描述
在这里插入图片描述

(图片为博主:"初阶牛"原创,未经允许,不得复制)

🔑非递归代码实现:

代码语言:javascript
复制
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s1;
        vector<int> v1;
        TreeNode*  cur=root;
        while(cur||!s1.empty()){
            //沿着左子树一直入节点
            while(cur){
                s1.push(cur);
                cur=cur->left;
            }

            TreeNode* top = s1.top();
            if(top==nullptr)break;
            v1.push_back(top->val);

            //栈顶元素出栈
            s1.pop();
            //右子树 以子问题的方式解决
            if(top->right)
            	cur=top->right;
        }
        return v1;
    }
};

三、非递归实现"后序遍历"

题目链接:传送门

题目描述: 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

二叉树的后序遍历指的是先访问左右子树,最后访问根节点的顺序遍历。即先遍历左子树,再遍历右子树,最后访问根节点。

后序遍历算法如下:

  1. 如果当前节点的左子树非空,则递归遍历左子树。
  2. 如果当前节点的右子树非空,则递归遍历右子树。
  3. 访问当前节点。

思路分析

对于后序遍历,同样注意存入容器的时机,应当是左子树和右子树都访问完毕,才能够访问根节点.

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

注意点: (1)访问结点之前,需要先判断右子树是否已经被访问.

如何判断根节点的右子树已经有没有访问? 答案: 上一个存入的结点是自己右子树,则右子树已经被访问. 上一个结点不是自己的右子树,则右子树未被访问.

示例:

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

💗非递归代码实现:

代码语言:javascript
复制
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s1;
        vector<int> v1;
        TreeNode* prv = nullptr;
        TreeNode* cur = root;
        while (cur || !s1.empty()) {
            //沿着左子树一直入节点
            while (cur) {
                s1.push(cur);
                cur = cur->left;
            }

            TreeNode* top = s1.top();
            if (top == nullptr)break;
            //右子树 以子问题的方式解决
            if (prv!=top->right && top->right) {
                cur = top->right;
                continue;
            }     
            prv=top;
            v1.push_back(top->val);
            //栈顶元素出栈
            s1.pop();
        }
        return v1;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-10-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 一、非递归实现"前序遍历"
    • 方法一、思路分析:
      • 🍔非递归代码实现1:
        • 方法二、思路分析
          • 🍉非递归实现2:
          • 二、非递归实现"中序遍历"
            • 思路分析:
              • 🔑非递归代码实现:
              • 三、非递归实现"后序遍历"
                • 思路分析
                  • 💗非递归代码实现:
                  相关产品与服务
                  容器服务
                  腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档