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

Python 二叉树非递归后序遍历

Python 二叉树非递归后序遍历，是指在遍历二叉树的时候，采用非递归的方式，按照“左右根”的顺序来遍历二叉树的节点。它的实现原理是：首先将根节点入栈，然后每次从栈中弹出一个节点，并将它的左右孩子节点依次入栈，最后将弹出的节点访问。

实现步骤

1、首先将根节点入栈；

2、从栈中弹出一个节点，并将它的左右孩子节点依次入栈，如果该节点的右孩子节点已经入栈，则将该节点出栈；

3、重复步骤 2，直到栈为空，结束遍历；

示例代码

1234567891011121314151617181920212223242526272829303132333435

def post_order_traversal(root):
if not root:
return
stack = []
node = root
last_visited = None
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
node = peek_node.right
else:
print(peek_node.val)
last_visited = stack.pop()

以上代码实现了 python 二叉树非递归后序遍历的功能，具体步骤如下：

1、首先定义一个栈，将根节点入栈；

2、从栈中弹出一个节点，判断它的左孩子节点是否存在，如果存在，将左孩子节点入栈，如果不存在，则判断它的右孩子节点是否存在；

3、如果右孩子节点存在，将右孩子节点入栈；如果右孩子节点不存在，则将弹出的节点访问；

4、重复步骤 2，直到栈为空，结束遍历；