如何分析python二叉树非递归版后序遍历

今天就跟大家聊聊有关如何分析python二叉树非递归版后序遍历，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

二叉树的非递归版后序遍历，首先定义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二叉树非递归版后序遍历有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注行业资讯频道，感谢大家的支持。