二叉树的先序遍历代码非递归

### 非递归实现二叉树先序遍历

对于非递归版本的先序遍历，可以通过显式使用栈来模拟函数调用的过程。下面是一个完整的 Python 实现：

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


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

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.value)

        if node.right:
            stack.append(node.right)
        
        if node.left:
            stack.append(node.left)

    return result

在这个实现中，每次从栈顶取出当前节点并将其值加入结果列表；接着按照先右后左的方式依次将子节点压入栈内，这样可以确保在下一次迭代时左侧分支会被优先处理。

相关问题

二叉树先序遍历非递归

### 二叉树先序遍历非递归实现

对于二叉树的先序遍历，当采用非递归方式时，通常会利用栈这一辅助数据结构来保存尚未处理过的节点。具体来说，在进入左子树之前应先访问根节点并将其压入栈内，随后继续向左深入直到遇到最左边叶子节点为止；接着回溯至上一层次尝试转向右侧分支重复上述过程直至整个树被完全遍历。

下面给出Python语言下的非递归先序遍历代码实例：

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


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

    stack, output = [root], []
    
    while stack:
        node = stack.pop()
        if node is not None:
            output.append(node.value)

            # 注意这里的顺序：因为栈是后进先出，
            # 所以应该先把右边的孩子放入栈中,
            # 这样可以保证下一次循环的时候先进入的是左边孩子.
            if node.right:
                stack.append(node.right)
                
            if node.left:
                stack.append(node.left)

    return output

此段程序定义了一个`TreeNode`类用于构建二叉树节点，并实现了名为`preorder_traversal`函数来进行非递归形式的先序遍历操作[^3]。

用代码非递归创建二叉树，并且实现非递归先序遍历和非递归中序遍历

下面是用 Python 语言实现的非递归创建二叉树和非递归遍历的代码示例：

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

def createTree(nums):
    if not nums:
        return None
    root = TreeNode(nums[0])
    stack = [root]
    i = 1
    while i < len(nums):
        node = TreeNode(nums[i])
        if not stack:
            break
        if stack[-1].left is None:
            stack[-1].left = node
        else:
            stack[-1].right = node
            stack.pop()
        stack.append(node)
        i += 1
    return root

def preorderTraversal(root):
    if not root:
        return []
    result = []
    stack = [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

def inorderTraversal(root):
    if not root:
        return []
    result = []
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        result.append(node.val)
        node = node.right
    return result

这里我们用到了栈来实现非递归遍历。在创建二叉树时，我们用一个栈来保存节点，如果当前节点的左子树为空，就将其作为左子树；否则，看是否有右兄弟节点，如果有，就将当前节点弹出栈，并将其右兄弟节点作为新的当前节点；如果没有，就继续将新节点作为左子树。

在先序遍历中，我们将根节点压入栈中，然后弹出栈顶元素，将其值加入结果数组中，再将其右子节点、左子节点依次压入栈中。在中序遍历中，我们需要一直将左子节点压入栈中，直到没有左子节点了，就取出栈顶元素，将其值加入结果数组中，并将当前节点设置为其右子节点，继续进行遍历。