精华内容
下载资源
问答
  • 递归遍历二叉树(后序遍历) 在二叉树的遍历中,分为递归遍历与非递归遍历。非递归遍历的执行效率较高,时间复杂度小,因此采用非递归遍历有利于提高代码运行效率。 //后序遍历非递归实现 void ...

    非递归遍历二叉树(后序遍历)

    在二叉树的遍历中,分为递归遍历与非递归遍历。非递归遍历的执行效率较高,时间复杂度小,因此采用非递归遍历有利于提高代码运行效率。

    //后序遍历非递归实现 
    void PostOrderTraversal(BinTree BT) {
        BinTree T , PrePop = NULL; //PrePop记录上一个Pop出来的结点
        Stack S = CreatStack(MaxSize);//	创建堆栈 
        T=BT;
        while (T || !IsEmpty(S)) {
            while (T) {        //一直向左将结点压入堆栈
                Push(S, T);
                T = T->Left;
            }
            //将Pop的过程改为循环
            while (!IsEmpty(S)) { //后序遍历有两种情况可以Pop该结点
                T = Pop(S);
                if (T->Right == PrePop || T->Right == NULL) {  //该结点的右结点为空或
         //       者上一次Pop的是该结点的右结点
                   printf("%05d", T->Data);
                    PrePop = T;
                }
                else {  //若不满足以上两种情况 说明该节点右侧节点还未被Pop
                    Push(S, T);  //则将该结点重新压回堆栈
                    T = T->Right;  //然后指向该结点的右节点
                    break; //退出Pop循环
                }
            }
        }
        
    

    后序遍历需要访问左子树->右子树->根 所以要Pop某个根结点的条件是右结点已经被Pop或者右结点为NULL,
    如果不满足条件,则说明右侧结点还未被Pop,继续进行循环(PrePop变量记录上一个Pop的结点,并用于判断是不是当前结点的右结点)


    后序遍历的Pop过程可以是连续的,直到有不满足条件的结点出现才停止Pop过程,所以写成循环。

    展开全文
  • 递归遍历二叉树 1.前言 ​ 总所周知,二叉树的遍历分为先序遍历、中序遍历和后序遍历。遍历的顺序不同,则结果不同。而遍历方法也分递归和非递归。而二者的复杂度相同:时间复杂度为O(nlgn),空间复杂度为O(n) 。 ...

    非递归遍历二叉树

    1.前言

    ​ 总所周知,二叉树的遍历分为先序遍历、中序遍历和后序遍历。遍历的顺序不同,则结果不同。而遍历方法也分递归和非递归。而二者的复杂度相同:时间复杂度为O(nlgn),空间复杂度为O(n)

    ​ 虽然递归的二叉树逻辑简单,但是通过递归调用可能会浪费多余的栈空间资源,因此非递归遍历也是十分有用的,相比起递归遍历,其会占用更少的栈资源。

    2.非递归遍历的实现

    ​ 非递归遍历二叉树是通过循环来实现的,在逻辑上相比起递归要稍微复杂一些,需要借用到stack(栈)数据结构。因为遍历时必须根节点往子节点循环,因此我们需要某类容器来存储上次循环节点的值,而栈这种类型数据结构恰恰能满足我们所需。

    ​ 那么如何利用栈来实现二叉树的非递归遍历呢?

    ​ 如果一个二叉树只有三个节点:根节点、左子节点、右子节点。那么所谓的先序遍历,就是先输出根节点、再输出左子节点、再输出右子节点;同理中序遍历,是输出左子节点、根节点、右子节点;后序遍历…。那么我们可以将三个节点按照我们想要的顺序依次推入栈中,再弹出,就能对三个节点进行先、中、后序遍历。例如:

    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
     };
    
    //三节点二叉树的先序输出
    stack<TreeNode *> sta;
    //中序和后序,只需要修改入栈的顺序
    sta.push(root->right);
    sta.push(root->left);
    sta.push(root);
    cout<<(sta.top())->val<<endl;
    sta.pop();
    cout<<(sta.top())->val<<endl;
    sta.pop();
    cout<<(sta.top())->val<<endl;
    sta.pop();
    

    ​ 那假设现在给这个二叉树的左子节点赋予左、右子节点,使得二叉树变为5节点的二叉树。那么原来3节点二叉树的先序遍历:根、根左、根右——就变成:根、根左、左左、左右、根右。会发现原来根节点的左子节点扩展成了三个,也就是包含了其左右子节点,而如果只看左子节点和它的子节点会发现,它们三个的顺序也是:根、左、右。

    ​ 我们现在可以得出一个结论,所谓的先序遍历、中序遍历、后序遍历不过是对一个节点以及它的左右子节点的遍历顺序罢了。那么我们把每三个节点:根、左、右当做一个整体,根据弹出栈的顺序,在循环遍历的时候将三个节点入栈,就能得到我们想要的遍历顺序。以下提供一种循环遍历二叉树的方法:

    ​ 该方法需要注意的一点:每个节点会被弹出两次栈,第一次被弹出是为了将左右子节点或者父节点入栈,第二次弹出是真正将其输出。

    //先序非递归遍历
    sta.push(root);//先把根节点入栈
    map<TreeNode*,bool> m;//定义一个键值对,用来判别该节点是否弹出过一次栈
    m.insert(make_pair(root,false));//如果值为false,则未被弹出过栈
    while(!sta.empty())//如果栈空,则说明遍历完成
    {
        p = sta.top();//弹出栈
        if(p == NULL)
            continue;
        sta.pop();
        
        if(m[p] == true)//如果值为true,则之前被弹出过一次栈
        {
            vec.push_back(p->val);
        }
        else
        {
            if(p->right != NULL)//右子节点入栈
            {
                m.insert(make_pair(p->right,false));
                sta.push(p->right);
            }
            if(p->left != NULL)//左子节点入栈
            {
                m.insert(make_pair(p->left,false));
                sta.push(p->left);
            }
            m[p] = true;//第一次弹出栈,将值设为true
            sta.push(p);//再次入栈
        }
    }
    

    ​ 以上是先序非递归遍历,如果需要中序、后序遍历,只需要修改入栈顺序。

    展开全文
  • 二叉树递归算法虽然简单,但是会导致时间复杂度比较高,下面给大家带来用栈实现的二叉树递归算法首先定义好二叉树,和元素类型为二叉树的栈typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, ...

    二叉树的递归算法虽然简单,但是会导致时间复杂度比较高,下面给大家带来用栈实现的二叉树非递归算法

    首先定义好二叉树,和元素类型为二叉树的栈

    typedef struct BiTNode{
        TElemType    data;
        struct BiTNode *lchild, *rchild;
    }BiTNode,*BiTree;
    
    typedef BiTree SElemType;
    typedef struct{
        SElemType *base;
        SElemType *top;
        int stacksize;
    }SqStack;
    
    
    

    然后实现栈的方法

    #include"1.h"
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    using namespace std;
    
    //初始化栈
    Status InitStack(SqStack &s){
        s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
        if(!s.base)exit(OVERFLOW);
        s.top=s.base;
        s.stacksize=STACK_INIT_SIZE;
        return OK;
    
    }
    //取栈顶元素
    Status GetTop(SqStack s,SElemType &e){
        if(s.top=s.base)
        return ERROR;
        e=*(s.top-1);
        return OK;
    }
    
    //元素入栈
    Status Push(SqStack &s,SElemType e){
        if(s.top-s.base>=s.stacksize){
            s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
            if(!s.base)exit(OVERFLOW);
            s.top=s.base+s.stacksize;
            s.stacksize+=STACKINCREMENT;
        }
        *s.top++ =e;
        return OK;
    
    }
    
    //取栈顶元素,并使top指针下移(也就是出栈)
    Status Pop(SqStack &s,SElemType &e){
        if(s.top==s.base)return ERROR;
        e=*--s.top;
        return OK;
    }
    
    //判断栈是否
    Status StackEmpty(SqStack &s){
        if(s.top==s.base)return TURE;
        else 
        return FALSE;
    }
    

    然后通过栈的操作遍历二叉树

    Status InOrderTraverse(BiTree T){
        SqStack sta;
        BiTree point;
        InitStack(sta);point=T;
        while(point||!StackEmpty(sta)){
            if(point){Push(sta,point);point=point->lchild;}
            else{
                Pop(sta,point);if(!Visit(point->data))return ERROR;
                point=point->rchild;
    
            }
        }
        return OK;
    }

    这样方法就写好了,想再检验一下方法可以在主函数中调用

    
    #include <iostream>
    #include"head2.h"
    using namespace std;
    
    
    int main() {
    BiTNode *BiTree;
        if(CreateBiTree(BiTree))
            cout<<"建树成功";
        else{
        }
        cout<<"\n中序非递归遍历二叉树";
        if(InOrderTraverse(BiTree))
            cout<<"遍历成功";
        else{}
            system("pause");
    }
    
    展开全文
  •   在之前学习的二叉树遍历(前文传送门)当中,其时间复杂度均为O(1)\mathcal{O}(1)O(1),而空间复杂度为O(n)\mathcal{O}(n)O(n),其或是利用递归调用栈或是数据结构中的栈结构来完成对树中节点的多次访问,也就是...

      在之前学习的二叉树遍历(前文传送门)当中,其时间复杂度均为O(1)\mathcal{O}(1),而空间复杂度为O(n)\mathcal{O}(n),其或是利用递归调用栈或是数据结构中的栈结构来完成对树中节点的多次访问,也就是利用了辅助空间来实现二叉树的遍历。

    1. 实现思路

    • 将当前所遍历到的节点记为curcur;
    • (1) 如果curcur无左孩子,则curcur迭代为其右子节点,即cur = cur->right;
    • (2) 如果curcur有左孩子,则curcur的左子树的最右叶子节点记为mostRightmostRight
      ① 如果mostRightmostRight的右孩子为空,则将右孩子指针指向当前所遍历的节点(mostRight->right = cur;),同时将当前所遍历的节点curcur遍历为其左孩子(cur = cur->left;);
      ② 如果mostRightmostRight的右孩子指向了当前所遍历的节点curcur(mostRight->right == cur;),将其右孩子指向空指针(mostRight->right = nullptr;),同时将当前所遍历节点curcur迭代为其右孩子节点(cur = cur->right;)。

    2. 代码实现

    void MorrisTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			}
    		} //(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    }
    

    3. 分析推导

    3.1 Morris遍历的规律和与递归栈方式的对比

    对下图的二叉树进行分析,可以看出如下规律:

    • (1) 左子树非空的节点会遍历两次
      ① 左子树的最右叶子节点为空时,该节点第一次遍历;
      ② 左子树的最右叶子节点非空时,该节点第二次遍历;
    • (2) 左子树为空的节点只遍历一次

    结合递归方法的二叉树遍历方式(如下代码),进行分析:

    void recursiveTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	//递归栈中的第一次遍历,此时进行输出打印则为前序遍历
    	//cout << root->val << ' ';
    	recursiveTraversal(root->left);
    	//递归栈中的第二次遍历,此时进行输出打印则为中序遍历
    	//cout << root->val << ' ';
    	recursiveTraversal(root->right);
    	//递归栈中的第三次遍历,此时进行输出打印则为后序遍历
    	//cout << root->val << ' ';
    }
    

    可以看到结合节点被遍历的次数,选择合适的输出打印时机,即可得到相应的遍历序列
    那么借鉴选择输出打印时机的这一思路,我们就可以较为便捷的实现MorrisMorris前序遍历和中序遍历了。

    3.2 Morris前序遍历

      在递归栈方式进行前序遍历的过程中,在首次遍历到节点的时候输出该节点的值,即可得到二叉树的先序遍历。

    那么我们要寻找到何时是二叉树中节点第一次遍历,经过3.13.1节的分析,我们发现:
      (1) 对于左子树不为空的节点,第一次遍历时机是其左子树的最右叶子节点为空的时候;
      (2) 对于左子树为空的节点,第一次遍历时机是 curcur在当前节点,且当前节点要迭代为curcur的右孩子节点 的时候;

    有了如上的分析,则可以实现MorrisMorris前序遍历,代码如下:

    void MorrisPreTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				//★★★时机(1):左子树不为空的节点第一次遍历
    				cout << cur->val << ' ';
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			} 
    		} else {
    			//★★★时机(2):左子树为空的节点第一次遍历
    			cout << cur->val << ' ';
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	cout << endl;
    }
    

    3.3 Morris中序遍历

      中序遍历和前序遍历的分析,其实就是个套娃过程,对于中序遍历,就是在第二次遍历节点的时机进行打印输出。而3.13.1节的分析中说了,对于左子树为空的节点只有一次遍历,思考一下,中序遍历的顺序是左中右,对于没有左子树的节点而言,其中序遍历和中右别无二样。所以其第一次遍历即可认为是第二次遍历。

    那么可以得到第二次遍历的时机如下:
      (1) 对于左子树不为空的节点,第二次遍历时机是其左子树的最右叶子节点不为空的时候;
      (2) 对于左子树为空的节点,第二次遍历时机是 curcur在当前节点,且当前节点要迭代为curcur的右孩子节点 的时候;

    代码如下:

    void MorrisInTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			} 
    		} else {
    			//★★★时机(1)&(2):左子树的最右叶子节点非空 或 左子树为空的节点第二(一)次遍历
    			cout << cur->val << ' ';
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	cout << endl;
    }
    

    3.4 Morris后序遍历

      对于后序遍历,就无法使用套娃了,因为递归栈方法中的第三次遍历根本就没有啊!!!思路是,使用左子树非空的节点的第二次遍历这个时间节点,①此时逆序输出其左子树的所有右边界边节点,②最后输出整棵二叉树的右边界边界点,至于为啥是可以这么来搞,确实得感叹青出于蓝而胜于蓝(据说Morris只在论文中给出了前序和中序的遍历方法,后序遍历是后来人搞出来的,只能大喊:真牛批!!!)

    画图分析一下,会发现确实是这么回事:

      就是这么神奇,同时注意到MorrisMorris算法实现是空间复杂度为O(1)\mathcal{O}(1)的,所以如何实现不使用辅助空间的限制下逆序打印左子树右边界这一要求呢,哦对了,就是使用链表反转的方法,这里的实现没有进行树的还原,其实,在使用中再调用一次该函数即可实现二叉树的还原。代码如下:

    TreeNode* reverseRightBdry(TreeNode* from) {
    	if(from == nullptr || from->right == nullptr) return from;
    	TreeNode *pre = nullptr, *next = nullptr;
    	while(from != nullptr) {
    		next = from->right; //next节点指向当前节点的右孩子节点
    		from->right = pre; //from的右孩子指针指向其父节点
    		//节点前移
    		pre = from;
    		from = next;
    	}
    	return pre;
    }
    

    那么有了逆序打印的功能实现,就可以完成MorrisMorris后序遍历的过程了,其中链表的反转过程只增加了时间复杂度n的常数系数,所以时间复杂度仍为O(n)\mathcal{O}(n),代码如下:

    void MorrisPosTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { //★★★时机:左子树非空的节点的第二次遍历的时间节点
    				printRightBdry(cur->left);
    				mostRight->right = nullptr;
    			} 
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	printRightBdry(root);//★★★时机:逆序输出整棵二叉树的右边界节点
    	cout << endl;
    }
    
    void printRightBdry(TreeNode* head) {
    	TreeNode* tail = reverseRightBdry(head); //对二叉树左子树右边界进行反转
    	TreeNode* cur = tail;
    	while(cur != nullptr) {
    		cout << cur->val << ' ';
    		cur = cur->next;
    	}
    	reverseRightBdry(tail); //对二叉树进行还原
    }
    
    展开全文
  • 如果直接用递归中序遍历存到数组中,然后输出,这样的时间复杂度是O(n) 为了只用O(h)的空间,我们采用非递归迭代策略。 思路: 能往左走就往左走,边走边入栈,直到不能走,弹出栈里元素往右走,重复之前操作。 ...
  • 其中遍历深度优先遍历(DFS)按照实现方法可以分为:递归遍历实现、非递归遍历实现、Morris遍历实现,文中只给了代码,没有对实现过程进行讲解,本文将对递归遍历实现、非递归遍历栈实现、Morris遍历实现这三类实现...
  • 由于本人之前已在此平台中发布了有关二叉树递归遍历算法的文档(链接见下),所以本篇博客本人主要讲述二叉树的非递归遍历算法。 二叉树递归遍历与相关统计 非递归遍历的基本原理 对递归调用有了初步了解的读者就...
  • 如果二叉树的节点数为N,则要求时间复杂度为O(N),额外空间复杂度为O(1)。 题解 之前的题目已经剖析过如何用递归和非递归的方法实现遍历二叉树,但是很不幸,之前所有的方法虽然常用,但都无法做到额外空间复杂度为O...
  • Morris神级遍历二叉树

    2020-11-21 11:46:32
    从而实现时间复杂度为O(N),而空间复杂度为O(1)的精妙算法。 morris遍历利用的是树的叶节点左右孩子为空(树的大量空闲指针),实现空间开销的极限缩减。 2.实质 避免使用栈结构,而是让下层到上层有指针,具体是...
  • o(n)时间复杂度,o(1)空间复杂度中序遍历二叉树做法:用一个last指针和一个cur指针。主要是查看是0.是否已经回到访问完的根节点1.从子节点回溯到当前节点 1.1 从左孩子回溯的:访问当前节点 1.2 从右孩子回溯的:...
  • 算法源码之非递归创建/遍历二叉树

    千次阅读 2012-08-04 13:19:17
    递归创建二叉树很简单,主要使用系统提供的栈... 同样,本文没有分析其原理、以及算法的时间、空间复杂度,这些东西在设计算法的时候要考虑,  将其现于纸上,繁琐。 #include #include #define SIZE 8 typ
  • Morris算法遍历二叉树

    2017-02-17 13:45:19
    遍历二叉树常用的方法是使用递归或者堆栈迭代实现 堆栈实现遍历的时间复杂度是O(n) 空间复杂度为O(logn) 使用递归算法时,空间复杂度为O(logn) 在节点数目较多时,递归的开销很大,占用资源大,因为需要不断的开辟新...
  • Morris 遍历二叉树

    2019-10-05 20:49:14
    相比使用栈或者递归(也是通过栈空间)方法,Morris 方法可以在空间复杂度为 O(1),时间复杂度为 O(n) 的条件下实现对二叉树遍历。 前序遍历 如果当前节点左孩子 cur->left 为空,输出当前节点 cur 并指向右...
  • 我们知道遍历二叉树可以通过迭代和递归中序遍历,这两种遍历使用O(H)的空间存储栈空间,时间复杂度O(N),Morris算法可以牺牲时间复杂度,空间复杂度为O(1). 其实遍历二叉树最大的困难是在子节点遍历完如何回到父...
  • Morris遍历的二叉树遍历算法的超强进阶算法,该算法可以将非递归遍历中的空间复杂度降为O(1)。从而能够实现时间复杂度为O(N),空间复杂度为O(1)的精妙算法。普通的递归于非递归的解法,其中都使用了栈的结构,...
  • 遍历二叉树的算法中的基本操作是访问结点,则不论按哪一种次序进行遍历,对n个结点的二叉树,其时间复杂度均为O(n)。 所需辅助空间为遍历过程中栈的最大容量,即树的深度,最坏情况下为n, 则空间复杂度也为O(n)。 ...
  • Morris遍历空间复杂度为O(1)的二叉树遍历算法通常我们对于二叉树进行遍历时,使用递归遍历或是基于栈来遍历,这两种方法都拥有最差为O(n)的空间复杂度(递归方法会在递归调用上浪费更多的时间),以及O(n)的时间复杂度...
  • Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间)。 通常,在实现二叉树的前序、中序和后序遍历时,有两种常用方法,一种是递归,一种是使用栈+迭代。这两种方法都是O(n)的空间复杂度递归本身占用栈...
  • Morris遍历二叉树

    2016-06-13 08:51:37
    通常,我们遍历一颗二叉树都会采用递归的方式,即前序遍历、中序遍历和后序遍历,这三种方法的时间复杂度为O(N),空间复杂度为O(logN);而Morris算法遍历一颗二叉树时间复杂度为O(2N),空间复杂度为O(1).可以...
  • Morris遍历二叉树 算法的时间复杂度O(N),N为结点的个数,但是空间复杂度是O(1)。对比递归的方法,递归实现的额外空间复杂度O(N),需要申请栈。 可以这么说,所有二叉树做遍历的解的最优解都是二叉树遍历。 Morris遍历...
  • 1.非递归遍历(辅助栈) 时间复杂度:O(N) 空间复杂度:O(N) 由于每个节点都要进栈和出栈,所以时间复杂度为O(N),同样空间复杂度也为O(N),N为结点数。 2.递归遍历 时间复杂度:O(N) 空间复杂度:O(N) ...
  • 用简单的图示说明了一种易理解的非递归遍历二叉树的算 法,实现了此算法,并说明了它的正确性,分析了它的时间及空间复杂度
  • 给定一棵二叉树的头节点head,完成二叉的先序丶中序丶和后序遍历,如果二叉树的节点为N,要求时间复杂度为O(N),空间复杂度为O(1); 实际使用递归函数来完成遍历都是使用了栈函数,空间复杂度为O(h),h为二叉树的高度...
  • 算法-Morris遍历二叉树

    2020-06-28 20:06:49
    解决问题:在不使用栈不使用递归的情况下对二叉树按照先中后续方法进行遍历,空间复杂度为O(1),时间复杂度为O(n). 解决问题思路 1.初始化当前节点为current. 2.当前节点不为空: (1)当前节点没有左孩子,currrent=...
  • 二叉树的前中后序遍历(递归,非递归),时间复杂度为N,空间复杂度为N 思路: 1)二叉树的三种递归遍历,只是递归遍历树的时候,打印的时机不同,第一次遍历结点的时候打印,为先序遍历。第二次为中序,第三次为...
  •   对于时间复杂度O(n),只要每个点遍历一次,就没有什么问题,但一般的非递归二叉树遍历(深度优先搜索BFS等),都需要额外的O(n)空间作为队列、栈或是已输出元素表。(更夸张的是,我在查找有关资料时,竟然发现...
  • 其实之前的文章里已经记录了二叉树的递归/非递归遍历代码实现。但是由于 Morris 遍历可以实现最优的遍历方式,这无疑是在面试时遇到此问题非常加分的回答。 1、Morris 遍历的基本概念 Morris 遍历:时间复杂度 O...
  • 树的基础,必须会,该题只不过是层序遍历要求求一下层数。 题目 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。...时间复杂度O(N) AC代码 /** * De

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 549
精华内容 219
关键字:

时间复杂度递归遍历二叉树