二叉树节点的定义

  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None

构建二叉树

  1. def create_binary_tree(input_list=[]):
  2.     if input_list is None or len(input_list) == 0:
  3.         return None
  4.     data = input_list.pop(0)
  5.     if data is None:
  6.         return None
  7.     node = TreeNode(data)
  8.     node.left = create_binary_tree(input_list)
  9.     node.right = create_binary_tree(input_list)
  10.     return node

深度优先遍历

前序遍历

  1. def pre_order_traversal(root):
  2.     if root is None:
  3.         return 
  4.     print(root.val)
  5.     pre_order_traversal(root.left)
  6.     pre_order_traversal(root.right)
  7.     return root

中序遍历

  1. def in_order_traversal(root):
  2.     if root is None:
  3.         return
  4.     in_order_traversal(root.left)
  5.     print(root.val)
  6.     in_order_traversal(root.right)
  7.     return root

后序遍历

  1. def post_order_traversal(root):
  2.     if root is None:
  3.         return
  4.     post_order_traversal(root.left)
  5.     post_order_traversal(root.right)
  6.     print(root.val)
  7.     return root

广度优先遍历

层序遍历

  1. from queue import Queue
  2. def level_order_traversal(root):
  3.     queue = Queue()
  4.     queue.put(root)
  5.     while not queue.empty():
  6.         root = queue.get()
  7.         print(root.val)
  8.         if root.left is not None:
  9.             queue.put(root.left)
  10.         if root.right is not None:
  11.             queue.put(root.right)