How to analyze the non-recursive Post-order traversal of python binary Tree

Today, I will talk to you about how to analyze the sequence traversal of the non-recursive version of python binary tree. Many people may not know much about it. In order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

For the non-recursive post-order traversal of a binary tree, TreeNode is defined as follows:

"

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

Non-recursive post-order traversal ideas:

The cur pointer points to the node you are currently traversing to, if

Satisfaction case 1: if it is not None, and the left child is not None, then traverse along the left side until the condition is not met

If case 1 is not satisfied, either the cur is None, or the left child is None. In either case, the last element in the stack is first taken out, and then divided into two cases:

1. If the right child of cur is not None and has not visited it, it extends to the right subtree of cur to traverse.

two。 If you are not satisfied (either the cur does not have a right child, or the right child has visited it), in either case, you have to visit the cur node. After the visit, go out the stack and mark it as visited, while the currently accessed element is set to None.

The python code is implemented as follows:

"

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.rightfully visited:

Cur=cur.right

Stack.append (cur)

Else:

# do a visit

Visits.append (cur.val)

Stack.pop ()

Visited = cur

Cur=None

Return visits

The single test is as follows:

Root = TreeNode (1)

Root.left=TreeNode (2)

Root.left.left = TreeNode (4)

Root.right = TreeNode (3)

Vals = postOrderUsingStack (root)

Print (vals)

The result of the post-order traversal is as follows:

After reading the above, do you have any further understanding of how to analyze the post-order traversal of python binary tree non-recursive version? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.