Binary tree traversal (Python)

Traverse the binary tree###

#0 GitHub

https://github.com/Coxhuang/binary-tree-traversal

#1 surroundings##

Python3.7.3

#2 Start##

#2.1 Level Traversal###

#1 Thinking analysis

#2 Code####

# Definition for a binary tree node.classTreeNode:"""
 node
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None
classSolution:
 def levelOrderBottom(self, root):"""
  Level traversal
  : param root:Root node
  : return: list_node -> List 
        """

  queue_node =[root]  #queue
  list_node =[]  #In-order traversal to store the result list

  while queue_node:  #The queue is not empty,Keep looping

   node = queue_node.pop()  #Leave the team
   if not node: #Node is empty,Start from scratch,Do not put empty nodes in the result list
    continue
   list_node.append(node.val) #Store the node value in the result list
   queue_node.insert(0, node.left) #Left node first enters the queue
   queue_node.insert(0, node.right) #Join the team after the right node

  print(list_node)return list_node

#3 test####

Output

# Level traversal
[3,9,20,15,7]

#2.2 First order traversal

#1 Ideas

#2 Code####

# Definition for a binary tree node.classTreeNode:"""
 node
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  Preorder traversal
  : param root:Root node
  : return: list_node -> List
        """
  stack_node =[root]  #Stack
  list_node =[]  #First traverse the result storage list

  while stack_node: #Stack is not empty
   node = stack_node.pop() #Top node pop
   if not node: #Node is empty
    continue
   list_node.append(node.val) #Save the non-empty node value to the list
   stack_node.append(node.right) #The right node is pushed onto the stack first
   stack_node.append(node.left) #Push the stack after the left node
  print(list_node)return list_node
    
 def preOrderBottom_re(self, root):"""
  Preorder traversal recursion
  : param root:Root node
  : return: list_node -> List
        """
        
  if not root:return None
  print(root.val)
  self.preOrderBottom_re(root.left)
  self.preOrderBottom_re(root.right)

#3 test####

#2.3 In-order traversal###

#1 Ideas

#2 Code####

# Definition for a binary tree node.classTreeNode:"""
 node
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  In-order traversal non-recursive
  : param root:Root node
  : return: list_node -> List
        """
  stack_node =[]  #Stack
  list_node =[]  #In-order traversal result storage list
  node_p = root #Current node
  while stack_node or node_p: #The current node is not empty or the stack is not empty

   while node_p: #Move all the way to the left
    stack_node.append(node_p) #Node push
    node_p = node_p.left #Pointer left

   node = stack_node.pop() #Unstack
   list_node.append(node.val) #Get node data
   node_p = node.right #Get node
  print(list_node)return list_node
    
 def inOrderBottom_re(self, root):"""
  In-order traversal recursion
  : param root:Root node
  : return: list_node -> List
        """

  if not root:return None
  self.inOrderBottom_re(root.left)print(root.val)
  self.inOrderBottom_re(root.right)

#3 test####

#2.4 Post-order traversal

#1 Ideas

#2 Code####

# Definition for a binary tree node.classTreeNode:"""
 node
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  Post-order traversal non-recursive
  : param root:Root node
  : return: list_node -> List
        """
  stack_node =[root]
  list_node =[]while stack_node:
   node = stack_node.pop()if node.left: #Left child is not empty
    stack_node.append(node.left) #Left child pushes the stack
   if node.right: #Right child is not empty
    stack_node.append(node.right) #Right child push

   list_node.append(node.val) #Get the current pointer value

  list_node.reverse() #Negate
  return list_node
    
 def postOrderBottom_re(self, root):"""
  Post-order traversal recursion
  : param root:Root node
  : return: list_node -> List
        """

  if not root:return None
  self.postOrderBottom_re(root.left)
  self.postOrderBottom_re(root.right)print(root.val)

#3 test####