为何在二叉树或二叉搜索树中采用Morris遍历而非递归？

Great question! Let's unpack this because there's a critical misconception in your assumption about recursive traversal's space complexity—plus some key scenarios where Morris traversal shines even when time complexity matches.

First, let's clear up the space complexity point:

You noted both have O(n) time and O(1) extra space, but recursive traversals do not have O(1) space. Recursion depends on the program's call stack, which uses O(h) space where h is the height of the tree. For a skewed tree (think a linked-list-like tree), h equals n, so the stack uses O(n) space. Even for balanced trees, it's O(log n) space—not O(1). Morris traversal is the only standard method that truly achieves O(1) extra space no matter the tree's structure.

Now, here's why you'd pick Morris traversal over recursion:

• Memory-constrained environments: If you're working with systems where memory is at a premium (like embedded devices, low-memory servers, or real-time systems), the call stack overhead of recursion can lead to stack overflow, especially with deep trees. Morris uses only a handful of pointer variables, no stack or auxiliary data structures, making it far more memory-efficient in these cases.
• Reduced runtime overhead: Recursive calls come with hidden costs—saving stack frames, storing return addresses, and function call setup/teardown. Morris is an iterative approach that avoids all these overheads, making it faster in performance-sensitive applications where every cycle counts.
• In-place traversal needs: If you need to modify the tree during traversal (and optionally restore it afterward), Morris traversal is designed for this. It temporarily modifies right pointers to create "threads" to predecessor nodes, allowing traversal without extra space, then cleans up those modifications. Recursion can't do this without additional storage to track nodes.
• Foundational knowledge for threaded trees: Learning Morris traversal teaches you how threaded binary trees work—this is useful for scenarios where you need fast access to a node's predecessor or successor without traversing the tree again, which recursive methods can't support efficiently.

At the end of the day, recursion is great for its simplicity and readability, but Morris traversal is the tool to reach for when you need strict O(1) space or have constraints that make recursion impractical.

内容的提问来源于stack exchange，提问作者Abhi38