117.info
人生若只如初见

如何实现TreeNode的非递归遍历

要实现TreeNode的非递归遍历,可以使用迭代方法和栈数据结构。这里以二叉树的前序遍历、中序遍历和后序遍历为例进行说明。

首先定义一个简单的TreeNode类:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
  1. 前序遍历(根 -> 左 -> 右)
def preorder_traversal(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
  1. 中序遍历(左 -> 根 -> 右)
def inorder_traversal(root):
    if root is None:
        return []

    stack, result = [], []
    current = root

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

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result
  1. 后序遍历(左 -> 右 -> 根)
def postorder_traversal(root):
    if root is None:
        return []

    stack, result = [root], []

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

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

    return result[::-1]  # 反转列表得到正确的后序遍历顺序

这样就实现了二叉树的非递归遍历。注意这里的遍历顺序与递归遍历相同,只是实现方式不同。

未经允许不得转载 » 本文链接:https://www.117.info/ask/fe772AzsOCAFXBg.html

推荐文章

  • TreeNode在图形界面中的应用场景

    TreeNode 是一个用于表示树形结构中节点的类 文件系统:在文件浏览器或文件管理器中,可以使用树形结构来展示文件和文件夹。每个节点可以表示一个文件或文件夹,...

  • 如何优化TreeNode的内存占用

    要优化TreeNode的内存占用,可以采取以下策略: 使用更小的数据结构:在某些情况下,可以考虑使用更小的数据结构来表示节点。例如,如果你不需要存储额外的信息,...

  • TreeNode在树形结构中的存储方法

    在树形结构中,TreeNode 是一个用于表示节点的类。每个节点包含一个值(如整数、字符串等)以及指向其子节点的引用。树形结构可以使用不同的存储方法,以下是两种...

  • 如何实现TreeNode的递归遍历

    要实现TreeNode的递归遍历,你可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法。这里我将分别介绍这两种方法的实现。
    首先,我们需要定义一个TreeNo...

  • KeyValuePair在数据结构中的分类

    KeyValuePair是C#中用于表示键值对的数据结构,属于System.Collections.Generic命名空间。它通常用于表示单个键值对,例如在枚举的上下文中或当需要从方法返回多...

  • 如何实现KeyValuePair的序列化和反序列化

    要实现KeyValuePair的序列化和反序列化,你可以使用C#中的System.Runtime.Serialization命名空间
    using System;
    using System.IO;
    using System....

  • KeyValuePair在不同编程语言中的实现差异

    KeyValuePair 是一种通用的数据结构,用于表示键值对。在不同的编程语言中,它可能有不同的实现方式和名称。以下是一些常见编程语言中 KeyValuePair 的实现差异:...

  • KeyValuePair在大数据处理中的应用

    KeyValuePair在大数据处理中主要用于存储和管理单个键值对的数据结构,其应用主要体现在以下几个方面: 数据存储:在大数据处理中,KeyValuePair可用于存储从数据...