树是用来模拟具有树状结构性质的数据集合。根据它的特性可以分为非常多的种类,对于我们来讲,掌握二叉树这种结构就足够了,它也是树最简单、应用最广泛的种类。

二叉树是一种典型的树树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

# 二叉树遍历

重点中的重点,最好同时掌握递归和非递归版本,递归版本很容易书写,但是真正考察基本功的是非递归版本。

根据前序遍历和中序遍历的特点重建二叉树,逆向思维,很有意思的题目

# 二叉树的对称性

# 二叉搜索树

二叉搜索树是特殊的二叉树,考察二叉搜索树的题目一般都是考察二叉搜索树的特性,所以掌握好它的特性很重要。

  1. 若任意节点的左⼦子树不不空,则左⼦子树上所有结点的值均⼩小于它的 根结点的值;
  2. 若任意节点的右⼦子树不不空,则右⼦子树上所有结点的值均⼤大于它的 根结点的值;
  3. 任意节点的左、右⼦子树也分别为⼆二叉查找树。

# 二叉树的深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

平衡二叉树:左右子树深度之差大于1