非递归遍历二叉树的源代码

非递归遍历二叉树的常见做法是使用栈来模拟递归过程。实现过程中，我们需要先将根节点压入栈中，然后循环执行以下操作：

1. 取出栈顶元素，并将其访问（输出或处理）；
2. 将栈顶元素的右子树（如果有）压入栈中；
3. 将栈顶元素的左子树（如果有）压入栈中。

具体代码如下：

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]:
    if not root:
        return []

    stack = []
    res = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right

    return res

以上是中序遍历的代码，前序遍历和后序遍历也可以使用类似的方式实现。只需要在访问节点的时候改变顺序即可。

相关问题

用递归、非递归两种方法遍历二叉树的源代码

递归遍历二叉树的代码：

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

def inorder(node: Node):
    if node is None:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

def preorder(node: Node):
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

def postorder(node: Node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

非递归遍历二叉树的代码：

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

def inorder(node: Node):
    stack = []
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            print(node.val)
            node = node.right

def preorder(node: Node):
    stack = [node]
    while stack:
        node = stack.pop()
        if node:
            print(node.val)
            stack.append(node.right)
            stack.append(node.left)

def postorder(node: Node):
    stack1 = [node]
    stack2 = []
    while stack1:
        node = stack1.pop()
        if node:
            stack2.append(node)
            stack1.append(node.left)
            stack1.append(node.right)
    while stack2:
        node = stack2.pop()
        print(node.val)

这里给出了中序、前序、后序三种遍历方式的代码，分别用递归和非递归的方式实现。