13518219792
今天就跟大家聊聊有关如何分析python二叉树非递归版后序遍历，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
成都创新互联是专业的长岛网站建设公司，长岛接单;提供网站制作、成都网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行长岛网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
二叉树的非递归版后序遍历，首先定义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)
后序遍历的结果如下：
看完上述内容，你们对如何分析python二叉树非递归版后序遍历有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。
