二叉树的非递归遍历代码

二叉树的非递归遍历常用的方法有两种，一种是使用栈，一种是使用 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 遍历方法只使用了常数级别的空间，因此在空间复杂度上优于基于栈的遍历方法。但是，由于需要修改树的结构，因此在时间复杂度上可能会劣于基于栈的遍历方法。