遍历树状结构的前向和后向方向
创始人
2024-12-04 06:30:15
0

遍历树状结构的前向和后向方向,一般可以使用递归或者迭代的方式来实现。下面是两种常用的解决方法,包含代码示例:

  1. 递归法: 递归法是一种常用的遍历树状结构的方法。在前向遍历时,先访问根节点,然后递归遍历左子树,最后递归遍历右子树。在后向遍历时,先递归遍历左子树,然后递归遍历右子树,最后访问根节点。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前向遍历
def preorder_traversal(root):
    if root is None:
        return
    print(root.val)  # 访问根节点
    preorder_traversal(root.left)  # 递归遍历左子树
    preorder_traversal(root.right)  # 递归遍历右子树

# 后向遍历
def postorder_traversal(root):
    if root is None:
        return
    postorder_traversal(root.left)  # 递归遍历左子树
    postorder_traversal(root.right)  # 递归遍历右子树
    print(root.val)  # 访问根节点
  1. 迭代法: 迭代法使用栈数据结构来辅助遍历树状结构。在前向遍历时,先将根节点入栈,然后循环弹出栈顶元素并访问,将其右子节点入栈,再将其左子节点入栈。在后向遍历时,先将根节点入栈,然后循环弹出栈顶元素并访问,将其左子节点入栈,再将其右子节点入栈。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前向遍历
def preorder_traversal(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val)  # 访问节点
        if node.right:
            stack.append(node.right)  # 先将右子节点入栈
        if node.left:
            stack.append(node.left)  # 再将左子节点入栈

# 后向遍历
def postorder_traversal(root):
    if root is None:
        return
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)  # 将节点值加入结果列表
        if node.left:
            stack.append(node.left)  # 先将左子节点入栈
        if node.right:
            stack.append(node.right)  # 再将右子节点入栈
    result.reverse()  # 反转结果列表
    for val in result:
        print(val)  # 访问节点

以上是两种常用的遍历树状结构的前向和后向方向的解决方法,包含了代码示例。具体选择哪种方法取决于实际需求和个人偏好。

相关内容

热门资讯

必胜教程!wepoke是是有挂... 必胜教程!wepoke是是有挂(wepoke模拟器)WepOke(总是真的有挂);WepOke软件透...
9分钟了解!九酷众娱真的有挂吗... 9分钟了解!九酷众娱真的有挂吗,多乐跑胡子辅助工具,玩家教你(有挂脚本)1、九酷众娱真的有挂吗ai机...
微扑克ai辅助!微扑克辅助器是... 微扑克ai辅助!微扑克辅助器是骗人,微扑克辅助是有(果然真的有挂)是一款可以让一直输的玩家,快速成为...
免费测试版!同城字牌外挂(透明... 免费测试版!同城字牌外挂(透明挂)确实真的是有挂(2020已更新)(哔哩哔哩);1、实时同城字牌外挂...
wepoke插件!wepoke... wepoke插件!wepoke管理系统(透视辅助)wePoke(一贯真的有挂);最新版2024是一款...
9分钟了解!心悦海南麻将有挂是... 9分钟了解!心悦海南麻将有挂是真的吗,天天福建十三张辅助工具,我来教教你(有挂软件)1.心悦海南麻将...
微扑克ai机器人!微扑克可以用... 微扑克ai机器人!微扑克可以用模拟器(透明挂)确实真的有挂1、实时微扑克开挂更新:用户可以随时随地访...
攻略讲解!赣牌圈的隐藏机制(透... 攻略讲解!赣牌圈的隐藏机制(透视辅助)好像是有挂(2022已更新)(哔哩哔哩)1、每一步都需要思考,...
总结教程!wepoke透明挂(... 总结教程!wepoke透明挂(wepok软件透明挂)wepoker(就是真的有挂);wepoker黑...
微扑克游戏辅助器!微扑克有挂,... 您好,微扑克这款游戏可以开挂的,确实是有挂的,需要了解加微【757446909】很多玩家在这款游戏中...