二叉树中序遍历_二叉树的中序序列

二叉树中序遍历_二叉树的中序序列二叉树是一种重要的数据结构,对于二叉树的遍历也很重要。这里通过三种方法简单介绍一下二叉树的中序遍历。中序遍历就是先遍历二叉树的左子树,然后遍历根节点,最后遍历右子树。例如下面的二叉树,中序遍历的结果如下:[5,10,6,15,2]对于中序遍历,直观上的结果就是将二叉树所有节点投影到下面的一条直线上,得到的顺序就是二叉树的中序遍历结果。1、递归法递归方法是最容易想到的方法。递归调用遍历方法先遍历左子

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

二叉树是一种重要的数据结构,对二叉树的遍历也很重要。这里简单介绍三种二叉树中序遍历的方法。二叉树的中序遍历就是首先遍历左子树,然后访问当前节点,最后遍历右子树。对于下面的二叉树,中序遍历结果如下:

二叉树中序遍历_二叉树的中序序列

结果:[5,10,6,15,2]

直观来看,二叉树的中序遍历就是将节点投影到一条水平的坐标上。如图:

二叉树中序遍历_二叉树的中序序列

1、递归法

这是思路最简单的方法,容易想到并且容易实现。递归的终止条件是当前节点是否为空。首先递归调用遍历左子树,然后访问当前节点,最后递归调用右子树。代码如下:

//recursive
class Solution1 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        inorderHelper(ret,root);
        return ret;
    }
private:
    void inorderHelper(vector<int>& ret,TreeNode* root)
    {
        if(root==NULL)return;
        inorderHelper(ret,root->left);
        ret.push_back(root->val);
        inorderHelper(ret,root->right);
    }
};

2、迭代法

在迭代方法中,从根节点开始找二叉树的最左节点,将走过的节点保存在一个栈中,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了。代码如下:

//iterate,using a stack
class Solution2 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        TreeNode *curr=root;
        stack<TreeNode*> st;
        while(!st.empty()||curr!=NULL)
        {
            while(curr!=NULL)
            {
                st.push(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            ret.push_back(curr->val);
            curr=curr->right;
        }
        return ret;
    }
};

这种方法时间复杂度是O(n),空间复杂度也是O(n)。

3、Morris法

这种方法是Morris发明的,看完之后感觉精妙无比。这种方法不使用递归,不使用栈,O(1)的空间复杂度完成二叉树的遍历。这种方法的基本思路就是将所有右儿子为NULL的节点的右儿子指向后继节点(对于右儿子不为空的节点,右儿子就是接下来要访问的节点)。这样,对于任意一个节点,当访问完它后,它的右儿子已经指向了下一个该访问的节点。对于最右节点,不需要进行这样的操作。注意,这样的操作是在遍历的时候完成的,完成访问节点后会把树还原。整个循环的判断条件为当前节点是否为空。例如上面的二叉树,遍历过程如下(根据当前节点c的位置):

(1)当前节点为10,因为左儿子非空,不能访问,找到c的左子树的最右节点p:

二叉树中序遍历_二叉树的中序序列

结果:[]

(2)找节点c的左子树的最右节点有两种终止条件,一种右儿子为空,一种右儿子指向当前节点。下面是右儿子为空的情况,这种情况先要构造,将节点p的右儿子指向后继节点c,然后c下移:

二叉树中序遍历_二叉树的中序序列

结果:[]

(3)当前节点c的左儿子为空,进行访问。访问后将c指向右儿子(即后继节点):

二叉树中序遍历_二叉树的中序序列

结果:[5]

(4)继续寻找左子树的最右节点,这次的终止条件是最右节点为当前节点。这说明当前节点的左子树遍历完毕,访问当前节点后,还原二叉树,将当前节点指向后继节点:

二叉树中序遍历_二叉树的中序序列

结果:[5,10]

(5)重复上述过程,直到c指向整棵二叉树的最右节点:

二叉树中序遍历_二叉树的中序序列

左儿子为空,进行访问,c转到右儿子。右儿子为空,不满足判断条件,循环结束,遍历完成。结果如下:

[5,10,6,15,2]

这就是Morris方法,时间复杂度为O(n),空间复杂度是O(1)。代码如下:

//Morris traversal,without a stack
class Solution3 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL)return ret;
        TreeNode *curr=root;
        TreeNode *pre;
        while(curr)
        {
            if(curr->left==NULL)
            {
                ret.push_back(curr->val);
                curr=curr->right;
            }
            else
            {
                pre=curr->left;
                while(pre->right&&pre->right!=curr)
                    pre=pre->right;
                if(pre->right==NULL)
                {
                    pre->right=curr;
                    curr=curr->left;
                }
                else
                {
                    ret.push_back(curr->val);
                    pre->right=NULL;
                    curr=curr->right;
                }
            }
        }
        return ret;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193806.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 基于UDP编程_udp详解

    基于UDP编程_udp详解基于UDP编程1UDP是数据报协议,无连接的,不可靠,追求传输效率的一种通信协议数据的发送和接收是同步的.在进行通信之前,不需要建立连接.其传输效率比TCP高.对其服务器而言,并没有三次握手的过程.因此和TCP相比,少了被动监听(listen)和(accept).只需要创建通信设备,绑定IP地址和端口号.然后进行数据的收发.1.服务器端的编程模型创建一个socket端点,返回该端点的文件描述符fdsocket(2)2)将fd和本地地址绑定bind(2)while(1){3)阻塞等待

  • 单射、双射与满射[通俗易懂]

    单射、双射与满射[通俗易懂]数学上,单射、满射和双射指根据其定义域和陪域的关联方式所区分的三类函数。单射:指将不同的变量映射到不同的值的函数。满射:指陪域等于值域的函数。即:对陪域中任意元素,都存在至少一个定义域中的元素与之对应。双射(也称一一对应):既是单射又是满射的函数。直观地说,一个双射函数形成一个对应,并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值。(在一些参考书中,“一一”用…

  • eclipse护眼颜色和字体大小设置[通俗易懂]

    eclipse护眼颜色和字体大小设置[通俗易懂]♣eclipse护眼颜色和关键字颜色设置♣eclipse字体大小设置(包括jsp,.xml,.java)1.Eclipse字体大小调整: 窗口(Window)-首选项(Prefer

  • JVM自动内存管理机制–读这篇就GO了

    之前看过JVM的相关知识,当时没有留下任何学习成果物,有些遗憾。这次重新复习了下,并通过博客来做下笔记(只能记录一部分,因为写博客真的很花时间),也给其他同行一些知识分享。Java自动内存管理机制包

  • pycharm配置github_怎么把git上放到pycharm

    pycharm配置github_怎么把git上放到pycharm1.下载git客户端2.FileàDefaultSettingàVersionControlàGit3.PathtoGitexecutable填写git客户端的git.exe路径,点击OK,如图下4.5.GitRepositoryURL的地址填写其形式如:http://gitlab.

  • goland2021.2激活破解3月最新在线激活

    goland2021.2激活破解3月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号