什么是二叉树？

二叉树是一种非线性数据结构，代表“祖先”和“后代”之间的派生关系。二叉树的基本单元和链表类似，也是节点，每个节点包含值，对左子节点的引用和对右子节点的引用。

1
2
3
4
5
6
class  TreeNode(val `val`: Int) {	//节点值
    // 左孩子节点
    val left: TreeNode? = null
    // 右孩子节点
    val right: TreeNode? = null
}

二叉树常用术语

  • 根节点、叶子节点、边：略。
  • 节点的度：该节点的子节点数量。
  • 节点的深度：从根节点到该节点所经过的边的数量。
  • 节点的高度：从距离该节点最远的叶节点到达该节点所经过的边的数量。

常见的二叉树类型

完美二叉树(满二叉树)

完美二叉树所有的节点都被填满，除了叶节点的度为0，其余所有节点的度都为2；若树的高度为h，则节点总数为2h+1-1。

完全二叉树

完全二叉树只有最底层的节点未被填满，且最底层节点尽量靠左填充。

平衡二叉树

平衡二叉树中任意节点的左子树和右子树的高度只差的绝对值不超过1。