二叉树

深度优先遍历

L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是二叉树 - 图1，二叉树 - 图2 为结点个数。
前序遍历( DLR )：

  1. def preorderTraversal(self, root: TreeNode) -> List[int]:
  2.     if not root:
  3.         return []
  4.     return (
  5.         [root.val]  # 中
  6.         + self.preorderTraversal(root.left)  # 左
  7.         + self.preorderTraversal(root.right)  # 右
  8.     )

中序遍历( LDR )：

  1. def inorderTraversal(self, root: TreeNode) -> List[int]:
  2.     if not root:
  3.         return []
  4.     return (
  5.         self.inorderTraversal(root.left)  # 左
  6.         + [root.val]  # 中
  7.         + self.inorderTraversal(root.right)  # 右
  8.     )

后续遍历( LRD )：

  1. def postorderTraversal(self, root: TreeNode) -> List[int]:
  2.     if not root:
  3.         return []
  4.     return (
  5.         self.postorderTraversal(root.left)  # 左
  6.         + self.postorderTraversal(root.right)  # 右
  7.         + [root.val]  # 中
  8.     )

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

  1. def levelOrder(self, root: TreeNode) -> List[List[int]]:
  2.     if not root:
  3.         return []
  4.     res, queue = [], [root]
  5.     while queue:
  6.         tmp, values = [], []
  7.         for node in queue:
  8.             values.append(node.val)
  9.             if node.left:
  10.                 tmp.append(node.left)
  11.             if node.right:
  12.                 tmp.append(node.right)
  13.         queue = tmp
  14.         res.append(values)
  15.     return res

二叉搜索数

二叉搜索树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；