Python Binary Tree 二叉树 数据结构

Question

基本概念

• 结点、父结点、子结点、兄弟结点；结点的度：结点的子树个数
• 层数、深度、高度、结点的度
• 满二叉树：除了叶结点，其它所有结点都有两个子结点（国内定义：除最后一层全为叶结点外，其它的层的每个结点都有两个子结点）
• 完全二叉树：除最后一层外，其它层全满，最后一层的叶结点必须从左到右填满

二叉树的遍历

class treeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

深度优先搜索（Depth First Search, DFS）

非递归的版本在完整代码中

前序遍历 PreOrder Traversal：根-左结点-右结点

def preorder(root):
  if root is None:
    return []
  return [root.val] + preorder(root.left) + preorder(root.right)

中序遍历 InOrder Traversal：左结点-根-右结点

后序遍历 PostOrder Traversal：左结点-右结点-根

广度优先搜索（Breadth First Search, BFS）

层次遍历 LevelOrder Traversal

def level_order(root):
  if not root:
    return []
  res = []
  nodequeue = [root]
  while nodequeue:
    root = nodequeue.pop(0)
    res.append(root.val)
    if root.left:
      nodequeue.append(root.left)
    if root.right:
      nodequeue.append(root.right)
  return res

时间复杂度：需要遍历每个结点，故为O(n)

空间复杂度：由于每个结点都要先进行存储再弹出，故空间复杂度为O(n)

二叉树的后序遍历，非递归版本：非递归的后序遍历是 hard 难度，所以专门在这里写一下。有下面几种思路：

前序遍历是“根-左-右”，稍微改一下，就可以变成“根-右-左”，而将最后的结果倒序输出，就是后序遍历“左-右-根”的顺序了。时间复杂度依然为 O(n)：

def postorder_wh1(root):
  if root is None:
    return []
  res = []
  nodestack = []
  while nodestack or root:
    if root:
      res.append(root.val)
      nodestack.append(root)
      root = root.right
    else:
      root = nodestack.pop()
      root = root.left
  # res1 用来存放 res 的倒序输出，也可以直接使用res[::-1]
  res1 = []
  for i in range(len(res)):
    res1.append(res.pop())
  return res1

使用两个栈实现，这个思路也比较易于理解。后序遍历是 左-右-根，所以对于一个栈来说，应该先 push 根结点，然后 push 右结点，最后 push 左结点：

def postorder_wh2(root):
  if root is None:
    return []
  res = []
  nodestack = [root]
  while nodestack:
    root = nodestack.pop()
    res.append(root)
    if root.left:
      nodestack.append(root.left)
    if root.right:
      nodestack.append(root.right)
  # 此时res中存放了倒序的结点，使用res1将其倒序输出并取结点的值
  res1 = []
  for i in range(len(res)):
    res1.append(res.pop().val)
  return res1