二叉树的中序遍历

难度：简单
给定一个二叉树的根节点 root ，返回它的中序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

Morris 遍历

思路：

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 $O(1)$。
Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 $x$）：

1. 如果 $x$ 无左孩子，先将 $x$ 的值加入答案数组，再访问 $x$ 的右孩子，即 $x=x.right$。
2. 如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，$x$ 在中序遍历中的前驱节点），我们记为 $predecessor$。根据 $predecessor$ 的右孩子是否为空，进行如下操作。
   • 如果 $predecessor$ 的右孩子为空，则将其右孩子指向 $x$，然后访问 $x$ 的左孩子，即 $x=x.left$。
   • 如果 $predecessor$ 的右孩子不为空，则此时其右孩子指向 $x$，说明我们已经遍历完 $x$ 的左子树，我们将 $predecessor$ 的右孩子置空，将 $x$ 的值加入答案数组，然后访问 $x$ 的右孩子，即 $x=x.right$。
3. 重复上述操作，直至访问完整棵树。

时间复杂度： $O(n)$，其中 $n$ 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)=O(n)$。
空间复杂度： $O(1)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        results = []
        most_right = None
        while root:
            most_right = root.left
            if most_right:
                while most_right.right and most_right.right != root:
                    most_right = most_right.right
                if not most_right.right:
                    most_right.right = root
                    root = root.left
                    continue
                else:
                    most_right.right = None
            results.append(root.val)
            root = root.right
        return results

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/