介绍

• 二叉树的结构
• 二叉树常考的原因有如下几点
  1、它可以结合链表、栈、队列和字符串等数据结构出题
  2、需要熟练掌握图的BFS，DFS遍历
  3、需掌握递归函数的使用，并根据题义自己设定递归过程
  4、工程上二叉树比较常用
• 面试中，默认二叉树只有数据项、左孩子指针、右孩子指针。
• 工程上常常会用到节点包含指向其父节点的二叉树。

相关概念

• 二叉树的子树：以二叉树中任意节点为根的子树
• 平衡二叉树(AVL)：二叉树中任意一颗子树的左右子树的深度差小于等于1（平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树，空树是平衡二叉树，平衡二叉树首先是二叉排序树）
• 搜索二叉树：二叉树中，每颗子树的左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点
• 红黑树、平衡搜索二叉树：这两种树都是搜索二叉树的不同实现，它们都提高了搜索二叉树的搜索效率，同时减少了调整为搜索二叉树的代价
• 满二叉树：除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,设二叉树的高度为L，节点树为N，则满足等式N = 2^L - 1的二叉树为满二叉树，满二叉树的高度可以根据L = log(N + 1)计算
• 完全二叉树(堆结构就是一种完全二叉树)：非满二叉树的完全二叉树的最后一层都集中在树的左边
• 后继节点：二叉树中序遍历中，该节点的下一个节点
• 前驱节点：二叉树中序遍历中，该节点的上一个节点
• 度：指的是一个节点拥有子节点的个数。如二叉树的节点的最大度为2。
• 深度：数的层数，根节点为第一层，依次类推。
• 叶子节点：度为0的节点，即没有子节点的节点。
• 哈夫曼树：带权路径长度达到最小的二叉树，也叫做最优二叉树。不关心树的结构，只要求带权值的路径达到最小值，哈夫曼树可能是完全二叉树也可能是满二叉树。

二叉树的性质

• 在二叉树中，第i层的结点总数不超过2^(i-1)；
• 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
• 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
• 具有n个结点的完全二叉树的深度为int（log2n）+1
• 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I<>1，则其父结点的编号为I/2；如果2I <= N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子；如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N，则无右儿子（根节点的编号为1）。
• (6)给定N个节点，能构成h(N)种不同的二叉树。
• h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

经典题

• 用递归和非递归的方式实现二叉树的先序、中序、后序遍历
  • ①非递归方式实现先序遍历
    具体过程：
    1、首先申请一个新的栈，记为stack。
    2、然后将头节点head压入stack中。
    3、每次从stack中弹出栈顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
    4、不断重复步骤3，直到stack为空，全部过程结束。
  • ②非递归方法实现中序遍历
    具体过程：
    1、申请一个新的栈，记为stack，申请一个变量cur，初始时令cur等于头节点。
    2、先把cur节点压入栈中，对以cur节点为头的整棵子树来说，依次把整棵树的左边界压入栈中，即不断令cur=cur.left，然后重复步骤2。
    3、不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点，记为node。打印node的值，并让cur=node.right，然后继续重复步骤2。
    4、当stack为空并且cur为空时，整个过程结束。
  • ③非递归方法实现后序遍历方法一：使用两个栈实现
    具体过程如下：
    1、申请一个栈，记为s1，然后将头节点压入s1中。
    2、从s1中弹出的节点记为cur，然后先把cur的左孩子压入s1中，然后把cur1的右孩子压入s1中。
    3、在整个过程中，每一个从s1中弹出的节点都放进第二个栈s2中。
    4、不断重复步骤2和步骤3，直到51为空，过程停止。
    5、从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序了。
  • ④非递归方法实现后序遍历方法二：使用一个栈实现
    具体过程如下：
    1、申请一个栈，记为stack，将头节点压入stack，同时设置两个变量h和c。在整个流程中，h代表最近一次弹出并打印的节点，c代表当前stack的栈顶节点，初始时令h为头节点，c为null。
    2、每次令c等于当前stack的栈顶节点，但是不从stack中弹出节点，此时分以下三种情况。
    （1）如果c的左孩子不为空，并且h不等于c的左孩子，也不等于c的右孩子，则把c的左孩子压入stack中。
    （2）如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中。
    （3）如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。
    3、一直重复步骤2，直到stack为空，过程停止。
  • 先序，中序和后序的递归算法如下：

# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreeToSequence:
    def fore_seq(self, root, result):
        if root != None:
            result[0].extend([root.val])
            self.fore_seq(root.left, result)
            self.fore_seq(root.right, result)
    def inter_seq(self, root, result):
        if root != None:
            self.inter_seq(root.left, result)
            result[1].extend([root.val])
            self.inter_seq(root.right, result)
    def back_seq(self, root, result):
        if root != None:
            self.back_seq(root.left, result)
            self.back_seq(root.right, result)
            result[2].extend([root.val])
    def convert(self, root):
        # write code here
        result = [[], [], []]
        self.fore_seq(root, result)
        self.inter_seq(root, result)
        self.back_seq(root, result)
        #以二维数组的形式返回先序、中序和后序遍历序列
        return result

不管是递归方法还是非递归方法，遍历整棵树的时间复杂度都是O（N），N为二叉树的节点数，额外空间复杂度为O（L），L为二叉树的层数。

• 判断以head为根的树是否为平衡二叉树
  采用后序遍历的思想，每次遍历某节点的左（右）子树时记录其是否为平衡二叉树，如果不是平衡二叉树则返回False，如果是平衡二叉树，则返回其树高，之后比较左右子树树高差距是否小于等于1，如果是，则以该节点为根的子树为平衡二叉树，否则不是平衡二叉树。

• 判断以head为根的子树书否为搜索二叉树
  中序遍历二叉树的同时判断当前节点是否小于中序后继节点，为了方便，采用非递归方法实现中序遍历

• 判断以head为根的二叉树是否为完全二叉树
  从左到右按层次遍历二叉树的同时用排除法判断，具体如下：
  1、如果当前节点只有右孩子，返回False
  2、如果当前节点只有左孩子，则如果后序节点有非叶子节点，则返回False
  3、如果遍历完整，没有返回False，则返回True

• 给定存在指向父节点的指针parent的二叉树，请返回给定节点node的后继节点。
  1、一般解法为先根据parent找到根节点，再中序遍历，这种解法时间和空间复杂度都是O(N)
  2、最优解可以做到时间复杂度为O(L)，L为node到其后继节点的实际距离，时间复杂度为O(1)：

  • 如果node有右子树，则其后继为其右子树的最左节点
  • 如果node无右子树，但它是其父节点的左子树，则其父节点为其后继
  • 如果node无右子树，且是其父节点的右孩子，则需要向上查找，目标为其父节点（包括隔代父节点）为其父节点的左子树，则其父节点的父节点就是node的后继（这时，node实际上是其后继节点左子树的最右节点）
  • 一直向上查找，直到空，如果没找到，则无后继

• 从下往上对折纸条，会在纸条上留下折痕，对折一次留下向下折痕，对折两次从上往下，依次为向下、向下、向上，给定对折次数N，请打印纸条展开后从上到下的折痕方向的序列
  第一次对折会留下一条向下的折痕，后序每对折一次，会在原来对折留下折痕的上下分别留下向下和向上的折痕，句子可知，折痕情况可以形式化为满二叉树的节点，节点值为折痕的方向，按右-中-左顺序遍历即可得到纸条从上到下的折痕序列，N为树高

• 给定搜索二叉树，头节点为head，其中有两个节点位置发生了调换，请打印被调换位置的节点
  中序遍历二叉树，则被调换节点出现在序列中出现降序的位置，且为第一次降序位置的较大节点和最后一次（可能只有一次降序）降序位置的较小节点。

• 给定二叉树，头节点为head，请返回所有节点间的最大距离
  某子树头节点为A，出现距离最大的三种情况：

  • 记左子树中所有节点和节点A的距离最大值为Lmax，记右子树中所有节点和节点A的距离最大值为Rmax，max1 = Lmax + 1 + Rmax。
  • 左子树中所有非头结点之间的最大距离：max2
  • 右子树中所有非头结点之间的最大距离：max3

  子树A的最大节点间距离为max1，max2，max3中的最大值
  根据以上分析，采用后序遍历的方式，具体如下：

  • 后序遍历二叉树，对当前节点进行2中的信息收集
  • 对左子树产生Lmax1（非根节点间的最大距离）和Lmax2（节点和左子树根节点间的最大距离）两个信息
    对右子树产生Rmax1（非根节点间的最大距离）和Rmax2（节点和右子树根节点间的最大距离）两个信息
  • 以当前节点为根的子树节点间的最大距离为max(Lmax1, Rmax1, Lmax2 + 1 + Rmax2)
  • Lmax2 + 1和Rmax2 + 1分别为当前节点左子树中节点到当前节点的最大值和当前节点右子树中节点到当前节点的最大值，需要返回

编程中返回两个信息可以通过返回长度为2的数组实现
在递归中维护当前层的处理结果并返回给上一层可以通过更新全局变量实现

• 已知二叉树头结点为head，其中所有节点都不一样，请返回含有节点数最多的搜索二叉树的头节点
  某子树头节点为A，出现搜索二叉树的两种情况：

  • 来自左子树中的搜索二叉树的头结点为左孩子且左子树上所有节点值小于A的节点值，来自右子树中的搜索二叉树的头结点为右孩子且右子树上所有节点值大于A的节点值，则以A为根的子树为搜索二叉树
  • 不满足以上情况则返回左、右子树中节点多的搜索二叉树

  根据以上分析，采用后序遍历的方式，具体如下：

  • 后序遍历二叉树，对每个节点进行如下信息收集
  • 对每个节点的左子树收集如下4个信息：左子树上最大搜索子树的头结点、节点个数、树上的最小值、树上的最大值。
  • 对每个节点的右子树收集如下4个信息：右子树上最大搜索子树的头结点、节点个数、树上的最小值、树上的最大值。
  • 根据前两步的信息判断是否满足出现搜索二叉树的两种情况

编程中返回四个信息可以通过返回长度为4的数组实现
在递归中维护当前层的处理结果并返回给上一层可以通过更新全局变量实现