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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java进阶之路

java面试热点:集合框架(二)

1950
来自专栏Java后端技术栈

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

1232
来自专栏程序生活

Leetcode-Easy 572. Subtree of Another Tree

572. Subtree of Another Tree 描述: 给定两个二叉树s和t,判断t是否s的一个子树。要求结构完全一致 ? ? 思...

3244
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2466
来自专栏云霄雨霁

字符串查找----R向单词查找树

1170
来自专栏IT可乐

Java数据结构和算法(十四)——堆

  在Java数据结构和算法(五)——队列中我们介绍了优先级队列,优先级队列是一种抽象数据类型(ADT),它提供了删除最大(或最小)关键字值的数据项的方法,插入...

37611
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

2948
来自专栏小二的折腾日记

LeetCode-49-Group-Anagrams

输入一个字符串数组,输出的是:将相同字符的字符串放在一个数组的二维数组。相同字符的处理,基本就是要对字符串排序的。然后需要考虑的就是排序好的那一个字符串怎么存的...

761
来自专栏一枝花算不算浪漫

Java中常见数据结构Map之LinkedHashMap

3283
来自专栏Java 源码分析

HashSet 源码分析

HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

3184

扫码关注云+社区

领取腾讯云代金券