上述代码递归反转的具体过程

`reverse`函数使用递归实现字符串反转，其具体过程如下：

1. 如果输入字符串的长度小于等于1，直接返回。

2. 否则，获取除去首尾字符的子串。

3. 对子串进行递归反转，得到反转后的子串。

4. 将首尾字符拼接到反转后的子串上，得到最终的结果。

举个例子，假设输入字符串为"hello"，其反转过程如下：

reverse("hello") -> reverse("ell") -> reverse("l") -> return
               <- reverse("lle") <- reverse("olle") <- return
                                       <- reverse("olleh") <- return

最终得到的结果是"olleh"，即"hello"反转后的结果。

相关问题

如何用递归实现链表反转

链表反转可以使用递归来实现，具体步骤如下：

1. 如果链表为空或只有一个节点，则直接返回该链表。

2. 对于当前链表，先用递归函数反转除第一个节点以外的其他节点，然后将第一个节点添加到反转后链表的末尾。

3. 返回反转后的链表。

下面是示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

在上述代码中，`head` 是当前链表的头节点，如果链表为空或只有一个节点，则直接返回该链表。否则，用递归函数反转除第一个节点以外的其他节点，并将第一个节点添加到反转后链表的末尾，最后返回反转后的链表。其中，`new_head` 是反转后的链表的头节点。

二叉树的非递归遍历代码

二叉树的非递归遍历常用的方法有两种，一种是使用栈，一种是使用 Morris 遍历。下面我将分别给出两种方法的 Python 代码实现。

## 栈实现非递归遍历

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorderTraversal(root):
    if not root:
        return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

def inorderTraversal(root):
    if not root:
        return []
    stack, res = [], []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            node = stack.pop()
            res.append(node.val)
            root = node.right
    return res

def postorderTraversal(root):
    if not root:
        return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

上述代码实现了二叉树的前序遍历、中序遍历和后序遍历，分别用 `preorderTraversal`、`inorderTraversal` 和 `postorderTraversal` 表示。这些函数的实现都是基于栈的非递归遍历方法，使用栈保存待访问的节点。在遍历时先将根节点入栈，然后循环执行以下操作：

- 弹出栈顶节点，记录其值；
- 将栈顶节点的右子节点（如果有）入栈；
- 将栈顶节点的左子节点（如果有）入栈。

由于栈的特性，上述循环会先访问左子树，然后是右子树，符合二叉树遍历的先左后右的规则。针对后序遍历，需要将结果数组反转。

## Morris 遍历实现非递归遍历

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorderTraversal(root):
    if not root:
        return []
    cur, res = root, []
    while cur:
        if not cur.left:
            res.append(cur.val)
            cur = cur.right
        else:
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if not pre.right:
                pre.right = cur
                cur = cur.left
            else:
                pre.right = None
                res.append(cur.val)
                cur = cur.right
    return res

上述代码实现了二叉树的中序遍历，使用 Morris 遍历方法。Morris 遍历方法基于线索二叉树的思想，利用空闲的指针保存访问过的节点，从而避免使用栈或者递归占用额外的空间。具体实现方法如下：

- 如果当前节点的左子节点为空，记录当前节点的值，然后将当前节点指向其右子节点；
- 如果当前节点的左子节点不为空，找到其左子树的最右节点，记为 `pre`；
- 如果 `pre` 的右指针为空，将其右指针指向当前节点，然后将当前节点指向其左子节点；
- 如果 `pre` 的右指针不为空，说明当前节点的左子树已经访问完毕，记录当前节点的值，然后将 `pre` 的右指针置为空，将当前节点指向其右子节点。

由于 Morris 遍历方法只使用了常数级别的空间，因此在空间复杂度上优于基于栈的遍历方法。但是，由于需要修改树的结构，因此在时间复杂度上可能会劣于基于栈的遍历方法。