二叉树的遍历分深度优先遍历（DFS）和宽度优先遍历（BFS）。其中深度优先遍历又分为先序遍历，中序遍历，后序遍历。因为二叉树是递归类数据结构，因此大部分关于二叉树的操作都可以通过递归实现。
先定义二叉树类：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None
遍历顺序：
前序遍历： root-left-right，根节点——左子节点——右子节点；
中序遍历： left-root-right，左子节点——根节点——右子节点；
后序遍历： left-right-root，左子节点——右子节点——根节点；
递归方法：
def traverse(root, order_type="preorder"): if not root: return if order_type=="preorder": print(root.val) traverse(root.left) if order_type=="inorder": print(root.val) traverse(root.right) if order_type=="postorder": print(root.val)
层次遍历：
def BFS(root): queue = [root] while queue: n = len(queue) for i in range(n): q = queue.pop(0) if q: print(q.val) queue.append(q.left if q.left else None) queue.append(q.right if q.right else None)
二叉树的最大深度
当前树的最大深度等于（1+max(左子树最大深度，右子树最大深度)）。
def maxDepth(root): if not root: return 0 return 1+max(maxDepth(root.left),maxDepth(root.right))
二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。可以通过递归求左右节点的最小深度的较小值，也可以层序遍历找到第一个叶子节点所在的层数。
class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 if not root.left and not root.right: return 1 if not root.right: return 1+self.minDepth(root.left) if not root.left: return 1+self.minDepth(root.right) return 1+min(self.minDepth(root.left),self.minDepth(root.right))
二叉树的所有路径
根节点到叶子节点的所有路径。
def traverse(node): if not node.left and not node.right: return [str(node.val)] left, right = [], [] if node.left: left = [str(node.val) + x for x in traverse(node.left)] if node.right: right = [str(node.val) + x for x in traverse(node.right)] return left + right