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表示存放节点值的结果列表。

先序遍历的非递归算法

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

1. 将根节点入栈。

2. 循环执行以下步骤，直到栈为空：

(1) 弹出栈顶元素，访问该节点。

(2) 如果该节点的右子树非空，则将右子树入栈。

(3) 如果该节点的左子树非空，则将左子树入栈。

例如，对于以下二叉树：

    1
   / \
  2   3
 / \
4   5

先序遍历的非递归算法的输出结果为：1 2 4 5 3。

具体的实现代码如下：

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