这个迭代中序遍历算法是众所周知的吗？

Question

我担心 Morris 遍历算法中的方法，并提出了在节点中使用父指针的更简单的解决方案。

限制如下：

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 实现：迭代

节点结构：

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        if self.left is not None:
            self.left.parent = self
        self.right = right
        if self.right is not None:
            self.right.parent = self
        self.parent = None

算法

1. Get the the leftmost node of the root of the tree.
2. Yield the node.
3. Check if the node has a right child.
4. If it has a right child, find the leftmost node of the right child.
5. If it doesn't have a right child
 i. Go up the tree until you find a node that is not right child of its parent.
 ii. Go to the parent of that node.
6. Repeat from step 2 until the node is None.

def iterative_inorder(root):
    cur = root
    # Navigate to the leftmost node
    while cur and cur.left:
        cur = cur.left

    while cur:
        yield cur.data

        # If right child exists, visit this subtree
        if cur.right:
            cur = cur.right
            while cur.left:
                cur = cur.left
        else:
            # Traverse back up to the parent
            while cur.parent and cur == cur.parent.right:
                cur = cur.parent
            cur = cur.parent

void iterativeInorder(Node* root) {
    Node* cur = root;

    // Find the leftmost node
    while (cur && cur->left) {
        cur = cur->left;
    }

    while (cur) {
        std::cout << cur->data << " "; // Output the data

        // Traverse the right subtree
        if (cur->right) {
            cur = cur->right;
            while (cur->left) {
                cur = cur->left;
            }
        } else {
            // Move up the tree
            while (cur->parent && cur == cur->parent->right) {
                cur = cur->parent;
            }
            cur = cur->parent;
        }
    }
}

我很好奇是否有人见过这样的实现（因为它过于简单），以及我是否应该将其发布到所有对不同算法感兴趣的人的地方，因为至少对我和我的同事来说这很有趣。

我在互联网上做了一些研究，基本上每个链接都涉及莫里斯遍历，所以我真的很好奇我是否能为算法解决方案做出自己的小贡献。如果有人看到非常相似的东西可以链接参考资料或类似的东西，我将不胜感激。谢谢大家！

Answer 1

如果有人看到非常相似的东西可以链接参考或类似的东西，我将不胜感激

来自维基百科：

实现类似目标的另一种方法是在每个节点中包含一个指向该节点的父节点的指针。鉴于此，总是可以到达“下一个”节点。当没有右子节点时，“右”指针仍然为空。要从右指针为空的节点查找“下一个”节点，请向上遍历“父”指针，直到到达右指针不为空的节点，并且该节点不是您刚刚出现的子节点。该节点是“下一个”节点，在它之后是其右侧的后代。

区别在于维基百科算法不会跳过节点，但其他方面非常相似。

（是的，你的算法会跳过节点。取一个没有右子节点的三节点树，如

root -> left child -> left grandchild

所示。最左边的节点是孙子节点。产生它。它没有右子节点，所以沿着树向上走到“左子节点”。该节点没有右子节点，因此转到其父节点（根节点）并生成该节点。仅生成两个节点。）