专栏首页算法channelLeetcode|二叉树非递归版后序遍历

Leetcode|二叉树非递归版后序遍历

二叉树的非递归版后序遍历,首先定义TreeNode如下:

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

非递归后序遍历思路:

cur指针指向当前正遍历到的节点,如果,

满足情况1:不为None,且左孩子不为None,则沿着左侧一直遍历,直到不满足条件;

如不满足情况1,说明要么cur为None,或者左孩子为None,不管哪种情况,都先拿出stack中的最后一个元素,又细分为两种情况:

1. cur的右孩子不为None,且未访问过,则伸向cur的右子树遍历

2. 若不满足(要么cur没有右孩子,要么右孩子访问过),不论哪种情况,都要访问cur节点了,访问后出栈,标记它为访问过,同时当前访问的元素置为None。


python代码实现如下:

""" post order using stack for binary tree """ def postOrderUsingStack(node=None): visits=[] stack = [] if node is None: return stack.append(node) cur = node visited=None while len(stack)>0: if cur is not None and cur.left is not None: stack.append(cur.left) cur = cur.left else: cur =stack[-1] # right child for current node is not None and is not visited if cur.right is not None and cur.right!=visited: cur=cur.right stack.append(cur) else: # do a visit visits.append(cur.val) stack.pop() visited = cur cur=None return visits


单测试如下:

root = TreeNode(1)

root.left=TreeNode(2)

root.left.left = TreeNode(4)

root.right = TreeNode(3)

vals = postOrderUsingStack(root)

print(vals)

后序遍历的结果如下:

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • pyecharts原来可以这样快速入门

    最近两天,翻看下pyecharts的源码,感叹这个框架写的真棒,思路清晰,设计简洁,通俗易懂,推荐读者们有空也阅读下。

    double
  • git|常用命令总结

    git help tutorial 获取常规的帮助指导 01 — 创建本地工作库 init 创建一个空的Git库或再次初始化当前库 clone ...

    double
  • 梯度提升树,分手快乐~

    GBDT 的全称是 Gradient Boosting Decision Tree,梯度提升树,在传统机器学习算法中,GBDT 算的上 TOP3 的算法。

    double
  • Navicat备份远程Oracle数据库到本地

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

    DannyHoo
  • Gear VR使用情况调查:仅10%的用户经常使用

    VRPinea
  • Fixed: MacOS Mojave(10.14) 解决终端用Crontab报权限问题(不管是Root还是普通用户)及Linux基础(shell)

    不管是用Root还是自身用户..都会报Operation not permitted(任务没法写入);

    CRPER
  • 使用IGV看序列比对情况

    本文从以下五个方面介绍了可视化序列比对数据和相关的tracks: 文件格式:推荐的是BAM/SAM,其他格式,并且需要进行sorting&indexing Re...

    生信技能树
  • 专家谈人工智能可能带来的安全威胁

    英国网络安全公司Darktrace的技术总监Dave Palmer在接受“Business Insider”杂志采访时谈到了人工智能可能带来的安全威胁,包括: ...

    人工智能快报
  • 插入数据

    双面人
  • Hexagon DSP 发布SDK 3.3.2,打造全新神经网络库

    将推理、场景分类、图像处理和视频回放增强之类的工作负载放到边缘设备(如智能手机)的CPU和GPU进行处理,会耗尽运行周期并缩短电池使用寿命。DSP编程越方便,您...

    BestSDK

扫码关注云+社区

领取腾讯云代金券