python先序遍历二叉树的非递归算法

以下是 Python 实现的二叉树先序遍历的非递归算法：

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
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

该算法利用栈来实现非递归遍历二叉树，先将根节点入栈，然后依次弹出栈顶元素，将其值添加到结果列表中，并将其右子节点和左子节点入栈。由于栈的后进先出特性，先把右子节点入栈，再把左子节点入栈，保证了先遍历左子树。

相关问题

先序遍历二叉树的非递归算法

先序遍历二叉树的非递归算法可以使用栈来实现。具体步骤如下：

1. 新建一个栈，将根节点入栈。

2. 当栈不为空时，执行以下操作：

a. 弹出栈顶元素，访问该节点。

b. 如果该节点的右子树不为空，将右子树入栈。

c. 如果该节点的左子树不为空，将左子树入栈。

3. 重复步骤2，直到栈为空。

代码实现如下：

def preorderTraversal(root):
    if not root:
        return []

    stack = [root]
    res = []
    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

其中，root表示二叉树的根节点，stack表示栈，res表示存放节点值的结果列表。

完成二叉树先序遍历的非递归算法的代码

以下是二叉树先序遍历的非递归算法的代码，使用栈来辅助实现：

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

def preorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []

    stack = [root]
    res = []
    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

其中，stack 是用来存储待遍历的节点的栈，res 是用来存储遍历结果的列表。先将根节点入栈，然后不断地从栈中弹出节点并访问它，如果该节点有右子节点，则将右子节点入栈，如果该节点有左子节点，则将左子节点入栈。这样就可以保证先访问左子节点，再访问右子节点，最后访问根节点，从而实现先序遍历。