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

二叉树中序遍历，一种方法是递归，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;
}

    

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