31 lines
1.2 KiB
Python
31 lines
1.2 KiB
Python
|
"""
|
|||
|
|
二叉树常见术语：
|
|||
|
|
|
|||
|
|
- 「根节点 root node」：位于二叉树顶层的节点，没有父节点。
|
|||
|
|
- 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向。
|
|||
|
|
- 「边 edge」：连接两个节点的线段，即节点引用（指针）。
|
|||
|
|
- 节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。
|
|||
|
|
- 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
|
|||
|
|
- 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。
|
|||
|
|
- 节点的「深度 depth」：从根节点到该节点所经过的边的数量。
|
|||
|
|
- 节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
class TreeNode:
|
|||
|
|
def __init__(self, val: int):
|
|||
|
|
self.val = val
|
|||
|
|
self.left: TreeNode | None = None
|
|||
|
|
self.right: TreeNode | None = None
|
|||
|
|
|
|||
|
|
|
|||
|
|
"""
|
|||
|
|
# 完美二叉树：除了叶节点，所有节点都有两个子节点，且左右节点数相同，
|
|||
|
|
若树的高度为h，则节点数为 2^(h+1)-1。也称为满二叉树
|
|||
|
|
|
|||
|
|
# 完全二叉树：只有最底层节点未被填满，且填充顺序从左到右
|
|||
|
|
|
|||
|
|
# 完满
|
|||
|
|
"""
|
|||
|
|
|