一、创建

二叉树结点类的定义：

# 二叉树的结点类
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

使用结点类可以直接创建一颗小型的二叉树做测试用：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(8)
root.left.left.right = TreeNode(9)
root.left.right.left = TreeNode(10)
root.left.right.right = TreeNode(11)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
root.right.left.left = TreeNode(12)
root.right.left.right = TreeNode(13)
root.right.right.left = TreeNode(14)
root.right.right.right = TreeNode(15)

1、从列表创建一颗二叉树

假设列表存放的是按层次遍历的树结点，比如根结点在 i 处，左右子树分别是 和。列表中的 '#' 表示空。比如 lst = ['1', '2', '3', '#', '4', '5']

# 用列表递归创建二叉树
def create_bt_list(lst, start=0):
    # 创建过程从根开始a开始，创左子树b，再创b的左子树，如果b的左子树为空，返回none。
    # 再接着创建b的右子树，
    if start < len(lst):
        if lst[start] == '#':
            return None  
        else:
            root = TreeNode(int(lst[start]))
            # 左子树
            root.left = create_bt_list(lst, 2 * start + 1)
            # 右子树
            root.right = create_bt_list(lst, 2 * start + 2)
            return root
    return None

2、从前序、中序遍历序列重建二叉树

前序遍历（根左右）和中序遍历（左根右）的结果中都不含重复的数字，例如前序遍历[1,2,4,7,3,5,6,8]和中序遍历[4,7,2,1,5,3,8,6]。

思路：前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为左子树的中序遍历结果，右部分为右子树的中序遍历的结果。根据左右子树的长度，可以从前序遍历的结果中划分出左右子树的前序遍历结果，接下来就是递归过程。（注意：必须序列中的值不重复才可以这么做）

def reconstuct_bt(pre, mid):
    if len(pre) < 1:
        return None
    root = TreeNode(pre[0])
    idx = mid.index(pre[0])
    root.left = reconstuct_bt(pre[1:idx+1], mid[0:idx])
    root.right = reconstuct_bt(pre[idx+1:], mid[idx+1:])
    return root

3、二叉树序列化与反序列化

空节点用 '#' 表示，节点之间用逗号分开。前序遍历结果就是一个序列化，反序列化也是前序遍历的顺序。

# 序列化
def Serialize(root):
    # write code here
    if not root:
        return '#'
    return str(root.val) + ',' + Serialize(root.left) + ',' + Serialize(root.right)

# 反序列化
global flag
flag = -1
def Deserialize(s):
    # write code here
    global flag
    flag += 1
    lst = s.split(',')
    # flag每次加1，从0开始，不能超过字符串长度，否则返回None
    if flag >= len(s):
        return None
    root = None
    # 新建一个树对象来反序列化字符串
    if lst[flag] != '#':
        # 往树中存值,递归输入s没问题，因为flag是不断增大的
        # 先反序列根结点然后左右
        root = TreeNode(int(lst[flag]))
        root.left = Deserialize(s)
        root.right = Deserialize(s)
    return root

二、遍历

对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即寻常所说的层次遍历。由于树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅易于理解并且代码非常简洁；当然也可以借助栈来实现非递归遍历。而对于广度遍历来说，需要使用队列进行非递归遍历。

四种基本的遍历思想为：

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点
• 层次遍历：仅仅需按层次遍历就可以

比如，求以下二叉树的各种遍历

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

1、前序遍历

非递归方法需要使用栈暂时存储子节点。先访问根结点，然后将右结点先入栈，然后再将左节点入栈，这样就能优先访问左节点。

# 递归方法
def pre_order(root):
    if root is None:
        return []
    mid = [root.val]
    left = pre_order(root.left)
    right = pre_order(root.right)
    return  mid + left + right

# 非递归方法
# 访问根结点 --> 右结点入栈 --> 左节点入栈
def pre_order2(root):
    if root is None:
        return []
    result = []
    stack = [root]
    # 使用栈保存子节点，先入后出，所以先放右结点
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

2、中序遍历

非递归方法也要用到一个栈，记录遍历回退的路径。中序遍历访问的第一个节点是从根结点开始沿着左子树一直走到左下角直到左节点为空，访问该节点然后指向节点的右子树，然后重复上面的过程，直至遍历完。遍历过程中，栈只是存放沿左边路的走过的节点，即使栈变为空，如果此时指针指向右结点，也要继续遍历。

# 递归方法
def in_order(root):
    if root is None:
        return []
    mid = [root.val]
    left = in_order(root.left)
    right = in_order(root.right)
    return  left + mid + right

# 非递归方法
def in_order2(root):
    if root is None:
        return []
    result = []
    stack = []
    p = root
    while p or stack:
        if p:
            stack.append(p)
            p = p.left
        else:
            node = stack.pop()
            result.append(node.val)
            p = node.right
    return result

3、后序遍历

网上的方法都很复杂，其实只要思路转换一下和前序遍历差不多。后序遍历是左右根，如果遍历时采用根右左的顺序然后再把结果转置就可以了。方法和前序遍历差不多。

# 递归方法
def post_order(root):
    if root is None:
        return []
    mid = [root.val]
    left = post_order(root.left)
    right = post_order(root.right)
    return  left + right + mid

# 非递归方法
def post_order2(root):
    if root is None:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

4、层次遍历

def layer_order(root):
    if root is None:
        return []
    result = []
    queque = [root]
    # 使用队列保存子节点，先入先出
    while queque:
        node = queque.pop(0)
        result.append(node.val)
        if node.left:
            queque.append(node.left)
        if node.right:
            queque.append(node.right)
    return result

拓展：把二叉树打印成多行

使用两个队列，分二级，第一级存当前行的节点，然后遍历当前行的节点保存节点值并且只要存在左右节点就存放到第二级队列中，该行遍历完后把该行的数据打印，把下一行的节点给当前队列，下一行置空。继续循环。

def multi_row_print(root):
    if not root:
        return []
    res = []
    nodes = [root]
    # width = 1   # 记录宽度用
    # depth = 0   # 记录层数用，可用来记录深度以及之字形打印
    while nodes:
        depth += 1
        vals = []
        queque = []
        for node in nodes:
            vals.append(node.val)
            if node.left:
                queque.append(node.left)
            if node.right:
                queque.append(node.right)
        nodes = queque
        # width = max(width, len(nodes))
        # if depth & 1 == 0:   # 之字形打印
        #     vals = vals[::-1]
        res.append(vals)
    return res

除了打印成多行还可以之字形打印，方法是可以使用一个变量记录当前的是第几行，奇数行不变，偶数行将结果反转打印，代码在上面的注释部分。

三、其他

1、二叉树的深度/宽度

深度即层次遍历的次数，一种方法是可以在多行打印二叉树时输出记录层数的变量 depth（多行打印注释部分），另一种思路是树的深度应该是左右子树深度较大的那个加1。

def tree_dpth(root):
    if root is None:
        return 0
    left = tree_dpth(root.left)
    right = tree_dpth(root.right)
    return max(left, right) + 1

宽度即层次遍历时最宽的那一层的节点个数，可以在分行打印时记录一下每层的宽度 width（多行打印注释部分）。

现在如果要问二叉树的最大宽度（包括空节点）是多少呢？

问题描述：

树的宽度是所有层中的最大宽度。满二叉树（full binary tree）是每个节点都有两个子节点，层数 k 与节点数 n 的关系式 n = 2^(k-1)。现在输入的二叉树不是满二叉树，但是要求出该二叉树最大宽度。每一层的最大宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的None节点也计入长度）之间的长度。

示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:
输入: 
        1
       / \
      3   2
     /     \  
    5       9 
   /         \
  6           7

输出: 8
解释: 最大值出现在树的第 4层，宽度为 8 (6,null,null,null,null,null,null,7)。

思路和多行打印差不多，同样是如果存在左右子节点就放到二级队列中，改变的地方是之前不计空节点所以返回每层的节点个数，而这里需要返回左右两个非空节点之间的宽度。如果能给每个节点一个编号，那么一层中所有节点的最右边的编号减去最左边的编号加1就是当前层的最大宽度。由于是类似于满二叉树，所以如果当前节点的编号是 i, 则其左右子节点的编号就是 2 * i 和 2 * i + 1。这样存放节点的同时存放一下编号就可以了。

def max_width(root):
    if not root:
        return []
    nodes = [(root, 1)]
    width = 0   
    while nodes:
        cur_wid = (nodes[-1][1] - nodes[0][1]) + 1
        width = max(width, cur_wid)
        queque = []
        for node in nodes:
            idx = node[1]
            if node[0].left:
                queque.append((node[0].left, 2*idx))
            if node[0].right:
                queque.append((node[0].right, 2*idx+1))
        nodes = queque
    return width

2、二叉树节点个数

def num_nodes(root):
    if root is None:
        return 0
    num_left = num_nodes(root.left)
    num_right = num_nodes(root.right)
    return num_left + num_right + 1

3、镜像/对称/平衡二叉树

镜像二叉树指的是二叉树所有节点的左右子节点（子树）交换位置。

 def mirror(root):
        if root is None:
            return 
        temp1 = root.left
        temp2 = root.right
        root.left = mirror(temp2)
        root.right = mirror(temp1)
        return root

对称二叉树指的是原二叉树和其镜像二叉树相同。方法是递归比较数的左子树与其右子树是否相同。

def isSymmetrical(root):
    return is_sym(root, root)

def is_sym(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    if root1.val != root2.val:
        return False
    return is_sym(root1.left, root2.right)

平衡二叉树指的是左右子树的深度差不超过1，利用上面的求深度函数，只要保证左右子树深度差不超过1就可以。

def is_balance_tree(root):
    if root is None:
        # 返回True是因为这是最后的判断依据，在不断递归中，最后是叶子节点，即终止，
        # 如果叶子节点时，依然左右子树之差小于1，那么就是平衡二叉树，返回True
        return True
    depth1 = tree_dpth(root.left)
    depth2 = tree_dpth(root.right)
    if abs(depth1 - depth2) > 1:
        return False
    return is_balance_tree(root.left) and is_balance_tree(root.right)

未完待续！