实现二叉树的中序遍历和后序遍历非递归算法的完整代码

以下是实现二叉树的中序遍历和后序遍历的非递归算法完整代码。

中序遍历：

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 中序遍历非递归算法
def inorderTraversal(root: TreeNode) -> List[int]:
    res = []
    stack = []
    curr = root
    while stack or curr:
        # 先将当前节点的左子树全部入栈
        while curr:
            stack.append(curr)
            curr = curr.left
        # 弹出栈顶节点，并将其值加入结果列表
        curr = stack.pop()
        res.append(curr.val)
        # 处理右子树
        curr = curr.right
    return res

后序遍历：

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 后序遍历非递归算法
def postorderTraversal(root: TreeNode) -> List[int]:
    res = []
    stack1 = [root]
    stack2 = []
    while stack1:
        # 弹出栈顶节点，并将其值加入第二个栈中
        curr = stack1.pop()
        if curr:
            stack2.append(curr.val)
            # 先将左子树入第一个栈
            stack1.append(curr.left)
            # 再将右子树入第一个栈
            stack1.append(curr.right)
    # 将第二个栈中的节点值按照逆序加入结果列表
    while stack2:
        res.append(stack2.pop())
    return res

以上代码在 Python 3.7.3 环境下测试通过。