首页 > 编程语言 > 详细

二叉树中序遍历Joseph M. Morris算法

时间:2021-08-30 00:40:55      阅读:30      评论:0      收藏:0      [点我收藏+]

二叉树中序遍历,一种方法是递归,leetcode上的非递归方法有一种是用栈实现的,想来也没多大优化,手动递归比自动递归也快不了多少。还有一种不用栈的非递归方法,是Joseph M. Morris发明的,这位元老就是KMP算法中的M。

下面代码来自贴吧大神,经测试可用。我还没研究具体是个怎么回事,时间上能达到100%

vector<int> inorderTraversal(TreeNode* p)
{
    vector<int> res;
    TreeNode* r = nullptr;
    while (p) {
        TreeNode* q = p->left;
        if (q) {
            while (q != r && q->right)
                q = q->right;
            if (q != r) {
                q->right = p;
                p = p->left;
                continue;
            } else
                q->right = NULL;
        }
        // printf("%d\n", p->val);
        res.push_back(p->val);
        r = p;
        p = p->right;
    }
    return res;
}

二叉树中序遍历Joseph M. Morris算法

原文:https://www.cnblogs.com/wangbingbing/p/15200403.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!