Shulou(Shulou.com)06/01 Report--

In this issue, the editor will bring you a python traversal about how to return. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

[title]

Given a binary tree, return its mid-order traversal.

Example:

Input: [1meme nullpene 2pas 3]

one

\

two

/

three

Output: [1, 3, 3, 2]

Advanced: the recursive algorithm is very simple, can you do it through the iterative algorithm?

[ideas]

Pre-order traversal, mid-order traversal and post-order traversal, in these three traversal methods, all refer to the order of the root nodes, and all traverse the left subtree and then the right subtree.

Middle order traversal recursive solution: first recursively traverse the left subtree, then access the value of the current node, and finally recursively traverse the right subtree.

The mid-order traversal non-recursive solution uses two stacks, one stack (stack 1) to store nodes, and the other stack (stack 2) to store access tags. To achieve the order of the left root and the right, you need to insert the right node first, then the root node, and finally the left node. The implementation steps are as follows: if the top node of stack 1 is not accessed, the node is popped up, and the right child node (if any) is added to the stack, and finally the left child node (if any) is added to the stack; at the same time, stack 2 adds the corresponding tag whether it is accessed or not.

[code]

Python version

Recursive solution

# Definition for a binary tree node.

# class TreeNode:

# def _ _ init__ (self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

Class Solution:

Def traverse (self, node):

If not node:

Return

# left root and right

Self.traverse (node.left)

Self.res.append (node.val)

Self.traverse (node.right)

Def inorderTraversal (self, root: TreeNode)-> List [int]:

Self.res = []

Self.traverse (root)

Return self.res

Non-recursive solution

Class Solution:

Def inorderTraversal (self, root: TreeNode)-> List [int]:

'non-recursive traversal''

If not root:

Return []

Stack = [root]

Visit = [0]

Res = []

While len (stack) > 0:

# has been traversed, put val into res

If visit [- 1] = = 1:

Res.append (stack.pop () .val)

Visit.pop ()

# if it has not been traversed, then traverse the left and right nodes (because it is a stack, save the right node first, and then save the left node)

Else:

Node = stack.pop ()

Visit_i = visit.pop ()

If node.right:

Stack.append (node.right)

Visit.append (0)

Stack.append (node)

Visit.append (1)

If node.left:

Stack.append (node.left)

Visit.append (0)

Return res above is the preface traversal of how to return python shared by Xiaobian. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.