一篇文章读懂系列-2.二叉树及常见面试题

大家通常认知的二叉树如下所示：

数据结构如下定义：

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

换成链表视角的话，可以这样看待二叉树：

可以理解成常规的链表只有一个next节点，二叉树有两个next节点，只不过我们把这两个next节点通常理解和表示成左孩子和右孩子。既然和链表性质很像，类比来看，可以认为二叉树基本继承了链表的一些性质：

①增加节点和删除节点的效率会比较高，随机访问效率会比较低。

②可以用递归来操作二叉树

实际上，绝大多数情况时候使用递归的形式来操作二叉树，具体做法是对二叉树的左子树和右子树递归进行操作即可。

下面是一些常见的练习或面试题，最好做到熟练掌握：

准备工作，通过函数创建上述二叉树：

arr = [10 ,6 ,4 ,-1, -1, 7, -1 ,9 ,-1 ,-1, 12 ,-1 ,16, 15 ,-1 ,-1 ,20, -1, -1]
def create_bin_tree(arr,i):
    if arr and i >= len(arr):
        return None,i
    if arr[i] == -1:
        return None,i
    tree = Node(arr[i])
    tree.left, j = create_bin_tree(arr,i+1)
    tree.right,k = create_bin_tree(arr,j+1)
    return tree,k

tree,_ = create_bin_tree(arr,0)

① 前序遍历：先打印当前节点，然后递归前序访问A，最后递归前序访问B，代码类似如下

def pre_order(tree):
    if not tree:
        return
    print(tree.val)
    pre_order(tree.left)
    pre_order(tree.right)

②中序遍历：先递归中序访问A，再打印当前节点，最后递归中序访问B,代码：

def mid_order(tree):
    if not tree:
        return
    mid_order(tree.left)
    print(tree.val)
    mid_order(tree.right)

③后续遍历：先递归后续遍历A，再递归后续遍历B，再访问当前节点

def post_order(tree):
    if not tree:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.val)

④求二叉树的高度： 先递归求A的高度，再递归求B的高度，取二者中最大值+1

def get_height(tree):
    if not tree:
        return 0
    left_height = get_height(tree.left)
    right_height = get_height(tree.right)
    return 1+max(left_height,right_height)

⑤求二叉树的镜像： 将当前节点的A和B部分互换，递归求A和B的镜像

def mirror(tree):
    if not tree:
        return None
    temp = tree.left
    tree.left = tree.right
    tree.right = temp
    mirror(tree.left)
    mirror(tree.right)
    return tree

⑥求二叉树的节点数：先求A的节点数，再求B的节点数，二者的和加1

def get_node_count(node):
    if not node:
        return 0
    left_node_count = get_node_count(node.left)
    right_node_count = get_node_count(node.right)
    return 1 + left_node_count + right_node_count

⑦求二叉树的叶子节点数：如果当前节点无孩子节点，则返回1；否则递归调用A和B的叶子节点并相加。

def get_leaf_count(node):
    if node == None:
        return 0
    if node.left == None and node.right==None:
        return 1
    return get_leaf_count(node.left)+get_leaf_count(node.right)

⑧广度遍历二叉树：初始化时，将二叉树的根节点放到队列中；后续每次从队列取一个节点，将其左右孩子放到队列中，接着递归调用即可。

def BFS(queue):
    if not queue:
        return
    node = queue[0]
    print(node.val)
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)
    del queue[0]
    BFS(queue)

queue = [tree]
BFS(queue)

⑨通过前序和中序构建二叉树：

前序：10 6 4 7 9 12 16 15 20

中序：4 6 7 9 10 12 15 16 20

核心思想：通过前序数组可以得知根节点，通过中序可以将根节点的左右孩子，也就是A和B找出来，然后递归调用即可。如下图所示：

本代码的主要细节是下标的处理，见下图所示：

代码如下：

def create_bin_tree_pre_mid(pre_trans,i,j,mid_trans,m,n):
    if i>j or m>n:
        return None
    pivot = pre_trans[i]
    s = m
    while s<=n:
        if mid_trans[s] == pivot:
            break
        s+=1
    node = Node(pre_trans[i])
    node.left = create_bin_tree_pre_mid(pre_trans,i+1,i+s-m,mid_trans,m,s-1)
    node.right = create_bin_tree_pre_mid(pre_trans,i+s-m+1,j,mid_trans,s+1,n)
    return node

tree2 = create_bin_tree_pre_mid(pre_trans,0,len(pre_trans)-1,mid_trans,0,len(mid_trans)-1)

从上面的例子也可以看出，学好递归的重要性，递归本身是一种自顶向下的思维方式，比较容易掌握，实际编程中也非常有用，值得我们练习和掌握。关于递归更深入的例子和探讨，可以查看笔者的算法求解思路培养系列。算法求解思路培养-2. 八皇后问题(说说递归） 算法求解思路培养-5.从递归到动态规划 算法求解思路培养-4.棋盘覆盖问题（递归终结篇） 算法求解思路培养-3.链表反转(链表和递归结合） 算法求解思路培养-6.动态规划之凸多边形剖分 算法求解思路培养-9.动态规划之最大连续子串和 算法求解思路培养-7.最长公共子序列问题求解（从递归到非递归）