精华内容
下载资源
问答
  • 力扣热门100题——二叉树的中序遍历递归,迭代,Morris 中序遍历
    2022-03-26 11:03:49

    7、二叉树的中序遍历

    1.问题描述

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

    2.示例

    示例 1:

    输入:root = [1,null,2,3]
    输出:[1,3,2]
    示例 2:

    输入:root = []
    输出:[]
    示例 3:

    输入:root = [1]
    输出:[1]

    3.提示

    树中节点数目在范围 [0, 100] 内
    -100 <= Node.val <= 100

    4.进阶

    递归算法很简单,你可以通过迭代算法完成吗?

    5.具体解法(递归,迭代,Morris 中序遍历)

    //方法一:递归
    //因为要返回一个遍历的结果,那么得要一个存储的容器,我们选择了ArrayList(不限长度,内容用泛型确定为Integer类型),示例的输出就是一个集合
    //采用递归的方法,就得有一个方法去被递归,inorder,参数是结点和存储遍历内容的集合
    //中序遍历是左,根,右,从根节点出发,如果根节点有左结点,就应该递归调用这个左子树的情况,直到这个此时迭代到的结点没有左子结点,把它存入集合中
    //存完了之后,再看这个根节点的右子结点情况如何,不断迭代就可以了
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res=new ArrayList<>();
            inorder(root,res);
            rerurn res;
        }
        public void inorder(TreeNode root,List<Integer>res){
            if(root==null){
                return;//这个return的效果就是,如果根节点为空,那么就应该不进行下面的操作,返回上一层调用
            }
            inorder(root.left,res);
            res.add(root.val);
            inorder(root.right,res);
        }
    }
    //方法二:迭代
    //迭代就不用方法去递归调用了,而是用一个栈去实现
    //递归实现时,是函数自己调用自己,一层层的嵌套下去,操作系统/虚拟机自动帮我们用 栈 来保存了每个调用的函数,现在我们需要自己模拟这样的调用过程。
    /*
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            Deque<TreeNode> stk = new LinkedList<TreeNode>();//创建一个栈
            while (root != null || !stk.isEmpty()) {//当根节点不为空或者栈不为空的时候,我们就应该去判断,如果是根节点不为空,那就往左子结点走
                while (root != null) {//直到左子结点是空了,就退出此while
                    stk.push(root);
                    root = root.left;
                }
                root = stk.pop();//将栈中最后存的那个结点取出,他就是整个树最左下角的结点,值放入集合中
                res.add(root.val);
                root = root.right;//然后将这个root变成右结点再去看对应这个层的右子树情况
            }
            return res;
        }
    }
    
     */
    
    //方法三:Morris 中序遍历
    //用递归和迭代的方式都使用了辅助的空间,而莫里斯遍历的优点是没有使用任何辅助空间。缺点是改变了整个树的结构,强行把一棵二叉树改成一段链表结构。
    //Morris 遍历算法是另一种遍历二叉树的方法,它能将非递归的中序遍历空间复杂度降为O(1)。
    //Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 x):
    
    //如果x无左孩子,先将x的值加入答案数组,再访问x的右孩子,即x=x.right。
    //如果x有左孩子,则找到x左子树上最右的节点(即左子树中序遍历的最后一个节点,x在中序遍历中的前驱节点),我们记为predecessor。
    //根据predecessor的右孩子是否为空,进行如下操作。
    //如果predecessor的右孩子为空,则将其右孩子指向x,然后访问x的左孩子,即x=x.left。
    //如果predecessor的右孩子不为空,则此时其右孩子指向x,说明我们已经遍历完x的左子树,我们将predecessor的右孩子置空,将x的值加入答案数组,然后访问x的右孩子,即 x=x.right。
    //重复上述操作,直至访问完整棵树。
    
    //其实整个过程我们就多做一步:假设当前遍历到的节点为x,将x的左子树中最右边的节点的右孩子指向x,
    //这样在左子树遍历完成后我们通过这个指向走回了x,且能通过这个指向知晓我们已经遍历完成了左子树,而不用再通过栈来维护,省去了栈的空间复杂度。
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            TreeNode predecessor = null;
    
            while (root != null) {
                if (root.left != null) {
                    // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                    predecessor = root.left;
                    while (predecessor.right != null && predecessor.right != root) {
                        predecessor = predecessor.right;
                    }
    
                    // 让 predecessor 的右指针指向 root,继续遍历左子树
                    if (predecessor.right == null) {
                        predecessor.right = root;
                        root = root.left;
                    }
                    // 说明左子树已经访问完了,我们需要断开链接
                    else {
                        res.add(root.val);
                        predecessor.right = null;//树是不能构成一个回路的,用这个算法就是用回路来实现指回root进行访问然后遍历右子树,
                                                 // 不然没办法回去;当不加这行代码的时候,可想这个二叉树已经不是二叉树了
                        root = root.right;
                    }
                }
                // 如果没有左孩子,则直接访问右孩子
                else {
                    res.add(root.val);
                    root = root.right;
                }
            }
            return res;
        }
    }
    

    对于方法三的一个补充理解:

    img

    我们将黄色区域部分挂到节点5的右子树上,接着再把2和5这两个节点挂到4节点的右边。
    这样整棵树基本上就变改成了一个链表了,之后再不断往右遍历。

    只要当前结点有左子节点,我们就把此结点和右子树都挂到左子结点的右下角,以此类推挂完了之后,再去遍历,而且遍历完每个左子树的时候,都要断开之前的一个挂的链接,恢复之前的形状

    6.收获

    • 遍历这种问题,都需要有一个返回值,这个时候得想用什么存储,这个是需要自己想到的

    • 递归的话,就得写一个方法去递归,而且得有出口

    • 复习了二叉树的中序遍历

    • 定义 inorder(root) 表示当前遍历到 \textit{root}root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 \textit{root}root 节点的左子树,然后将 \textit{root}root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 \textit{root}root 节点的右子树即可,递归终止的条件为碰到空节点。(中序遍历的思路)

    • 递归遍历太简单了

      前序遍历:打印 - 左 - 右
      中序遍历:左 - 打印 - 右
      后序遍历:左 - 右 - 打印
      题目要求的是中序遍历,那就按照 左-打印-右这种顺序遍历树就可以了,递归函数实现

      终止条件:当前节点为空时
      函数内:递归的调用左节点,打印当前节点,再递归调用右节点

    • 对于树、链表等有了新认识,就是树,链表等这种数据结构,我们在实现的时候是通过一个类来实现的,里面有(以树为例)值,左节点,右节点,还有构造方法,这样其实是一个结点,而通过一个又一个结点,这样组成了我们想表达的树,在使用的时候也是利用这几个成员变量去分析。

    • 对于树、链表等有了新认识,就是树,链表等这种数据结构,我们在实现的时候是通过一个类来实现的,里面有(以树为例)值,左节点,右节点,还有构造方法,这样其实是一个结点,而通过一个又一个结点,这样组成了我们想表达的树,在使用的时候也是利用这几个成员变量去分析。

    更多相关内容
  • 二叉树的遍历递归算法不常考,主要考察非递归❤ 先序、中序、后序遍历(递归) 递归算法的区别在于visit()函数的位置❤,代码以先序遍历为例,其顺序为根左右,if判断语句中符合这一规律,中序、后序按其左根右和...

    二叉树(BiTree)的遍历分为:
    先序遍历(preorder):根左右
    中序遍历(inorder):左根右
    后序遍历(postorder):左右根
    其中,时间复杂度和空间复杂度都是O(n),
    二叉树的遍历递归算法不常考,主要考察非递归❤

    先序、中序、后序遍历(递归)

    递归算法的区别在于visit()函数的位置❤,代码以先序遍历为例,其顺序为根左右,if判断语句中符合这一规律,中序、后序按其左根右和左右根的规律改变这三句代码的顺序即可。

    void preorder(BiTree T){ // 先序遍历递归算法
    	if(T!=NULL){  // 当二叉树的根节点不为空时
    		visit(T); // 先访问根节点❤
    		preorder(T->lchild); // 再访问左孩子
    		preorder(T->rchild);  // 最后访问右孩子
    	}
    }
    

    中序遍历(非递归)

    算法思想:非递归需要借助栈来实现,沿着根的左孩子一直向左走,将左孩子依次入栈,直到左孩子为空,然后从栈顶开始出栈,出栈的同时访问出栈结点,若有右孩子则等该出栈元素出栈后把他的右孩子入栈。
    图解与分析
    p指向根节点,q指向栈底
    在这里插入图片描述
    然后沿着左孩子一直走,并依次入栈,当走到D结点时,没有左孩子了。这时开始从栈顶出栈,此时的遍历序列为D,B。
    在这里插入图片描述
    D,B出栈后,此时p指向B结点,发现B还有右孩子,所以将右孩子出栈。此时的序列为D,B,E,此时栈里只剩一个A结点了。
    在这里插入图片描述
    然后继续将栈顶元素进行出栈并访问,此时序列为D,B,E,A,此时p指向A结点,发现A结点有右孩子,将右孩子进栈并出栈。此时二叉树遍历完毕,栈也为空,最终中序遍历结果为:DBEAC。
    在这里插入图片描述
    代码

    void Inorder(BiTree T){
    	InitStack(s); // 初始化一个栈s
    	BiTree *p=T;  // 将二叉树的根节点赋给指针p
    	while(p!=NULL || !IsEmpty(s)){ 
    	//❤ 二叉树不为空或栈不为空
    	// 即二叉树遍历完了栈也为空,才是真正的遍历完了,要不就像上面最后一张图,
    	// 栈空了,C还没进栈呢,就退出循环了。
    		if(p!=NULL){
    			push(s,p); // 左孩子依次,入栈
    			p=p->lchild;  // 左孩子不为空,向左一直走
    		}
    		else{
    			pop(s,p);  // 栈顶元素,出栈 
    			visit(p);
    			p=p->rchild;  // 访问右子树
    		}
    	}
    	free(s); 
    }
    

    注解
    push(s,x) 表示x入栈
    pop(s,y) 表示y出栈
    IsEmpty(A) 表示判断数列是否为空的函数
    InitStack(s) 表示初始化栈s

    展开全文
  • 由于不管是先序遍历还是中序遍历以及后序遍历,我们都需要利用一个辅助栈来进行每个节点的存储打印,所以每个节点都要进栈和出栈,不过是根据那种遍历方式确定节点的进栈顺序,所以时间复杂度为O(n),同样空间复杂度...

    非递归版:
    由于不管是先序遍历还是中序遍历以及后序遍历,我们都需要利用一个辅助栈来进行每个节点的存储打印,所以每个节点都要进栈和出栈,不过是根据那种遍历方式改变的是每个节点的进栈顺序所以时间复杂度为O(n),同样空间复杂度也为O(n),n为结点数
    层序遍历是通过队列来进行每个节点的存储打印的,所以时间复杂度和空间复杂度也与前三种遍历方式一样。
    递归版:
    空间复杂度与系统堆栈有关,系统栈需要记住每个节点的值,所以空间复杂度为O(n)。时间复杂度应该为O(n),根据公式T(n)=2T(n/2)+1=2(2T(n/4)+1)+1=2^logn+2^(logn-1)+...+2+1 ~= n,所以时间复杂度为O(n)。

    相关代码如下(包括递归版和非递归版)

    BiTree.h:

    #pragma once
    typedef char TElemType;
    typedef struct BiTNode 
    {
    	TElemType data;
    	struct BiTNode* Ichild, * rchild;
    }BiTNode,*BiTree;
    int CreateBiTree(BiTree& T);				//先序构造二叉树
    int PreOrderTraverse(BiTree T);				//先序遍历二叉树
    int InOrderTraverse(BiTree T);				//中序遍历二叉树
    int PostOrderTraverse(BiTree T);			//后序遍历二叉树
    int LevelOrderTraverse(BiTree T);			//层序遍历二叉树
    int PreOrderTraverse1(BiTree T);			//先序遍历二叉树,非递归版
    int InOrderTraverse1(BiTree T);				//中序遍历二叉树,非递归版
    int PostOederTraverse1(BiTree T);			//后序遍历二叉树,非递归版
    

    BiTree.cpp:

    #include "BitTree.h"
    #include<queue>
    #include<stack>
    #include<iostream>
    using namespace std;
    int CreateBiTree(BiTree& T)
    {
    	TElemType e;
    	cin >> e;
    	if (e == '#')//#表示空树
    		T = NULL;
    	else
    	{
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		if (!T)
    			exit(0);
    		else
    		{
    			T->data = e;//生成根节点
    			CreateBiTree(T->Ichild);//构造左子树
    			CreateBiTree(T->rchild);//构造右子树
    		}
    	}
    	return 1;
    }
    
    int PreOrderTraverse(BiTree T)//前序遍历
    {
    	if (T) { //判T是否为空树
    		cout << T->data; //输出T节点的数据
    		if (PreOrderTraverse(T->Ichild)); //递归遍历左子树
    		if (PreOrderTraverse(T->rchild)); //递归遍历右子树
    		return 0;
    	}
    	else
    		return 1;
    }
    
    int InOrderTraverse(BiTree T)//中序遍历
    {
    	if (T) {//判T是否为空树,递归边界
    		if (InOrderTraverse(T->Ichild));//递归遍历左子树
    		cout << T->data;//输出T节点的数据
    		if (InOrderTraverse(T->rchild));//递归遍历右子树
    		return 0;
    	}
    	else
    		return 1;
    }
    
    int PostOrderTraverse(BiTree T)//后序遍历
    {
    	if (T){//判T是否为空树
    		if(PostOrderTraverse(T->Ichild));//递归遍历左子树
    		if (PostOrderTraverse(T->rchild));//递归遍历右子树
    		cout << T->data;//输出T节点的数据
    		return 0;
    	}
    	else 
    		return 1;
    }
    
    int LevelOrderTraverse(BiTree T)//层序遍历
    {
    	if (T == NULL)
    		return 0;
    	queue<BiTree> Q;
    	Q.push(T);//把根结点推入
    	while (!Q.empty())//循环结束之后再次判断,直到队列为空
    	{
    		cout << Q.front()->data;
    		if (Q.front()->Ichild!= NULL)//左节点进队列
    			Q.push(Q.front()->Ichild);
    		if (Q.front()->rchild != NULL)//右节点进队列
    			Q.push(Q.front()->rchild);
    		Q.pop();//队头出列
    	}
    	cout << endl;
    	return 1;
    }
    
    int PreOrderTraverse1(BiTree T)//前序遍历
    {
    /*
    对于任一结点P:
    	1)访问结点P,并将结点P入栈;
    	2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;
    	3)直到P为NULL并且栈为空,则遍历结束。
    */
    	stack<BiTree> s;
    	BiTree p = T;//根节点
    	while (p != NULL || !s.empty())
    	{
    		while (p != NULL)//根左右
    		{
    			cout << p->data;
    			s.push(p);
    			p = p->Ichild;
    		}
    		if (!s.empty())
    		{
    			p = s.top();//得到根节点
    			s.pop();//根节点出栈
    			p = p->rchild;//
    		}
    	}
    	return 0;
    }
    
    int InOrderTraverse1(BiTree T)//中序遍历
    {
    /*
    对于任一结点P:
    	1)若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;
    	2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;
    	3)直到P为NULL并且栈为空则遍历结束
    */
    	stack<BiTree> s;
    	BiTree p = T;
    	while (p != NULL || !s.empty())
    	{
    		while (p != NULL)
    		{
    			s.push(p);
    			p = p->Ichild;
    		}
    		if (!s.empty())
    		{
    			p = s.top();//得到最底端的左节点
    			cout << p->data;//输出节点值
    			s.pop();
    			p = p->rchild;
    		}
    	}
    	return 0;
    }
    
    int PostOederTraverse1(BiTree T)//后序遍历
    {
    /*
    要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。如果P不存在左孩子和右孩子,则可以直接访问它;
    或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点。
    若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。
    */
    	stack<BiTree> s;
    	BiTree cur;//当前结点
    	BiTree pre = NULL;//前一次访问的结点
    	s.push(T);//根节点出栈
    	while (!s.empty())
    	{
    		cur = s.top();
    		if ((cur->Ichild == NULL && cur->rchild == NULL) ||
    			(pre != NULL && (pre == cur->Ichild || pre == cur->rchild)))
    		{
    			cout << cur->data;//当前结点没有孩子节点或孩子节点都已经被访问了
    			s.pop();
    			pre = cur;
    		}
    		else
    		{
    			if (cur->rchild != NULL)
    				s.push(cur->rchild);//右孩子先进栈
    			if (cur->Ichild != NULL)
    				s.push(cur->Ichild);//左孩子后进栈,保证在取栈顶元素时,左孩子在右孩子之前被访问
    		}
    	}
    	return 0;
    }
    

    test.cpp:

    #include"BitTree.h"
    #include<iostream>
    using namespace std;
    
    int main()
    {
    	cout << "输入二叉树:";
    	BiTree T;
    	CreateBiTree(T);
    	cout << "先序遍历(递归):\t";
    	PreOrderTraverse(T);
    
    	cout << "\n先序遍历(非递归):\t";
    	PreOrderTraverse1(T);
    
    	cout << "\n中序遍历(递归):\t";
    	InOrderTraverse(T);
    
    	cout << "\n中序遍历(非递归):\t";
    	InOrderTraverse1(T);
    
    	cout << "\n后序遍历(递归):\t";
    	PostOrderTraverse(T);
    
    	cout << "\n后序遍历(非递归):\t";
    	PostOederTraverse1(T);
    
    	cout << "\n层序遍历(非递归):\t";
    	LevelOrderTraverse(T);
    
    
    	//ABC##DE#G##F###
    	system("pause");
    }
    

    运行结果如下:

    在这里插入图片描述

    展开全文
  • 二叉树的中序遍历 题目描述: 解题思路: 第一种:递归。又是递归,可以发现很多题都可以用到递归的思路…。二叉树的中序遍历,这里不太了解的可以看看这个博客:二叉树遍历...时间复杂度:O(N) class TreeNode: def
  • 你可以运用递归和迭代两种方法解决这个问题吗? 代码: public boolean isSymmetric(TreeNode root) { if(root==null) { return true; } return dfs(root.left, root.right); } public

    给定一个二叉树,检查它是否是镜像对称的。

    例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
    在这里插入图片描述

    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    在这里插入图片描述

    进阶:

    你可以运用递归和迭代两种方法解决这个问题吗?

    代码:
    public boolean isSymmetric(TreeNode root) {
    		if(root==null) {
    			return true;
    		}
    		return dfs(root.left, root.right);
        }
    	public boolean dfs(TreeNode root1,TreeNode root2) {
    		if(root1==null&&root2==null) {
    			return true;
    		}
    		if(root1==null||root2==null||root1.val!=root2.val) {
    			return false;
    		}
    		return dfs(root1.left, root2.right)&&dfs(root1.right, root2.left);
    		
    	}
    

    在这里插入图片描述

    展开全文
  • 中序遍历顾名思义,就是先访问根节点,再访问左右孩子的遍历方法,对于一棵二叉树而言,我们可以采用递归和非递归的方法来实现对二叉树各节点的遍历递归方法实现简单,但对于空间复杂度要求较高;非递归方法虽然...
  • Morris中序遍历二叉树的中序遍历更好的空间复杂度 二叉树的中序遍历 二叉树的中序遍历遍历顺序是先从左子树开始,接下访问根节点,然后访问右子树,我自己为了方便记忆,就是想中序,就是下一个访问中间节点,也...
  • 时间复杂度5.结论 1.题目 二叉树中序遍历 2.数据结构与算法 递归: 迭代:引入辅助栈,处理递归嵌套问题。 3.源代码 模板类定义,参考我的文章:《二叉树BT 模板类实现》 这里只给出实现各版本中序遍历的代码。 ...
  • Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 x): 如果 x 无左孩子,先将 x 的值加入答案数组,再访问 x 的右孩子,即x=x.right 如果 x 有左孩子,则找到 x 左子树上最右的节点(即左子树中序遍历的最后...
  • 递归中序遍历算法 代码思考 算法技巧 实现代码 快照 评价算法 总结 欢迎关注算法思考与应用公众号 你会学到什么?树的递归遍历算法很容易理解,代码也很精简,但是如果想要从本质上理解二叉树常用的三种遍历方法...
  • 目录概述线索化二叉树的实现中序遍历构建中序线索化二叉树的遍历 概述 百度百科: 在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索...
  • 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,...
  • 进阶: 递归算法很简单,你可以通过迭代算法完成吗? 递归实现 递归遍历太简单了 前序遍历:打印-左-右 中序遍历:左-打印-右 后序遍历:左-右-打印 题目要求的是中序遍历,那就按照 左-打印-右这种顺序遍历树就可以了...
  • Morris 遍历算法是另一种遍历二叉树的方法,它能将非递归中序遍历空间复杂度降为 O(1) 缺点是改变了整个树的结构,强行把一棵二叉树改成一段链表结构。 我们将黄色区域部分挂到节点5的右子树上,接着再把2和5这两...
  • 算法递归中序遍历二叉树总结(2种方法) @author:Jingdai @date:2020.12.03 方法1 先序遍历是第一次遇到该节点遍历中序是第二次遇到该节点遍历;而后序是第三次遇到该节点遍历。非递归用栈进行遍历,第一次遇到...
  • 三种对应时间和空间复杂度 1. Iterative way (stack). Time: O(n), Space: O(n). 2. Recursive solution. Time: O(n), Space: O(n). 3. Threaded tree (Morris). Time: O(n), Space: O(1). 二叉树中序遍历 ...
  • 话不多说,前两种直接上代码: ...递归方法: void preOrder(TreeNode* root){ if(root != NULL){ preOrder(root->left); cout << root->val << " "; preOrder(root->right); } }...
  • 彻底搞懂递归时间复杂度

    千次阅读 2021-09-15 00:22:41
    笔者编码10载,面过很多程序员简历上写着熟悉数据结构和算法,但是对于时间复杂度稍微深入点的问题,都回答的不怎么样,其实还是没懂 搞懂算法时间复杂度是一个优先程序员的分水岭 先来看letcode一道题, 泰波那契...
  • 首先, 我们需要找到二叉树T中第一个被中序遍历的结点: 根据中序遍历算法逻辑, (※)也就是找到二叉树T的最左下结点. 下面的算法可定位到二叉树的最左下结点. BiTreeNode* FirstNode(BiTreeNode* T)//在以T为根...
  • 二叉树的中序遍历(递归和循环)使数据结构的一种基本知识,不做过多解释了,直接附上代码。 递归: void pre(TreeNode* root){//中序递归遍历 if(root != NULL){ pre(root->left); cout << root->...
  • 本文主要介绍二叉树中序遍历方法,其中包括了递归和迭代两种实现方式。 中序遍历:左子树-&gt;根节点-&gt;右子树(根节点在中间) 例如: 上图所示的二叉树的中序遍历顺序为:6 3 1 4 0 2 7 5 本文...
  • 中序遍历二叉树(递归、迭代、Morris算法) 三种算法时间、空间复杂度的比较: 算法 时间复杂度 空间复杂度 递归 O(n) O(n) 迭代 O(n) O(n) Morris O(n) O(1) 定义树节点 public class TreeNode { ...
  • 那么大家想一想递归算法的空间复杂度应该怎么分析呢。 我这里用一个到简单的题目来举例 题目:求第n的斐波那契数 相信使用递归算法来求斐波那契数,大家应该再熟悉不过了 代码如下: int fibonacci(int i) { if(i &...
  • C语言实现二叉树的中序遍历

    千次阅读 2020-10-12 16:52:18
    二叉树的中序遍历就是首先遍历左子树,然后访问当前节点,最后遍历右子树。对于下面的二叉树,中序遍历结果如下: 结果:[5,10,6,15,2] 直观来看,二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图: ...
  • 二叉树的中序遍历:按照访问左子树-根节点-右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整...
  • 中序遍历-三种解法 LeetCode94-二叉树的中序遍历 解法三参考自官方题解 解法一:递归 基础解法,很容易想到,也很好写。时空复杂度均为O(n) class Solution { public: vector<int> inorderTraversal...
  • 在「递归」地遍历某个子树的过程中,我们也是将这颗子树看成一颗全新的树,按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质,我们就可以得出本题的做法。 递归思路 对于任意一颗树而言,前序遍历的...
  • 二刷的时候感觉还是有点不太上手, 记录一下思路顺便三刷。 题目描述 思路描述 按照思考顺序 ...2.得到中序遍历的左子树长度之后,根据前序遍历的子树的第一个遍历点是根节点的特性就 可以再次带入前序
  • 构建二叉树可以使用前序遍历+中序,或者中序+后序,但是前序+后序无法构建,原因是前序遍历列表中,第一个元素一定是根节点,剩余的元素是左子树的前序遍历+右子树的前序遍历列表,即前序遍历结构为:[root+[left+...
  • 二叉树中序遍历递归算法详解

    千次阅读 2013-04-25 14:36:04
    二叉树中序遍历递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的中序遍历的特性,该二叉树中序遍历顺序为:DBGEACHFI; 2. 一般遍历一颗二叉树,先序中序或者后序,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,033
精华内容 28,413
关键字:

中序遍历递归算法时间复杂度