种类：
1. 满二叉树
2. 完全二叉树
3. 二叉搜索树
4. 平衡二叉树搜索树：又被称为AVL(Adelson-Velsky and Landis)树，且具有以下性质：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树
存储方式：
1.链式存储
2.顺序存储：父节点的数组下标是i,那么它的左孩子就是2 * i + 1,右孩子就是i * 2 + 2
遍历方式：
1.深度优先遍历:前序遍历、中序遍历、后续遍历
2.广度优先遍历
力扣题目
- 二叉树的前序遍历
- 二叉树的后序遍历
- 二叉树的中序遍历
- 二叉树的层序遍历
- 二叉树的层序遍历 II
- 二叉树的右视图
- 二叉树的层平均值
- N 叉树的层序遍历
- 在每个树行中找最大值
- 填充每个节点的下一个右侧节点指针
- 填充每个节点的下一个右侧节点指针 II
- 二叉树的最大深度
- 二叉树的最小深度
- 翻转二叉树
- N 叉树的前序遍历
- N 叉树的后序遍历
对称二叉树
力扣二叉树经典面试题1
力扣二叉树经典面试题2
二叉树链式存储结构
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
}
1. 二叉树的前序、中序、后续遍历
前序遍历
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var result: [Int] = []
guard let root = root else { return result } // 如果根节点为空，直接返回空数组
// 递归实现前序遍历
preorderTraversalHelper(root, &result)
return result
}
func preorderTraversalHelper(_ node: TreeNode, _ result: inout [Int]) {
if let node = node {
// 访问根节点
result.append(node.val)
// 遍历左子树
preorderTraversalHelper(node.left, &result)
// 遍历右子树
preorderTraversalHelper(node.right, &result)
}
}
//中序遍历
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var result: [Int] = []
guard let root = root else { return result } // 如果根节点为空，直接返回空数组
// 递归实现中序遍历
inorderTraversalHelper(root, &result)
return result
}
func inorderTraversalHelper(_ node: TreeNode, _ result: inout [Int]) {
if let node = node {
// 遍历左子树
inorderTraversalHelper(node.left, &result)
// 访问根节点
result.append(node.val)
// 遍历右子树
inorderTraversalHelper(node.right, &result)
}
}
后续遍历
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var result: [Int] = []
guard let root = root else { return result } // 如果根节点为空，直接返回空数组
// 递归实现后序遍历
postorderTraversalHelper(root, &result)
return result
}
func postorderTraversalHelper(_ node: TreeNode, _ result: inout [Int]) {
if let node = node {
// 遍历左子树
postorderTraversalHelper(node.left, &result)
// 遍历右子树
postorderTraversalHelper(node.right, &result)
// 访问根节点
result.append(node.val)
}
}
2. 二叉树的高度、节点数、最大深度、最小深度
高度 = 最大深度
func height(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 } // 如果根节点为空，返回 0
// 递归计算左子树和右子树的高度，然后取较大值加 1
let leftHeight = height(root.left)
let rightHeight = height(root.right)
return max(leftHeight, rightHeight) + 1
}
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 } // 如果根节点为空，返回 0
// 递归计算左子树和右子树的最大深度
let leftDepth = maxDepth(root.left)
let rightDepth = maxDepth(root.right)
// 返回左右子树中较大的深度加 1（根节点本身）
return max(leftDepth, rightDepth) + 1
}
节点数
func countNodes(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 } // 如果根节点为空，返回 0
// 递归计算左子树和右子树的节点数，然后相加并加上根节点本身
let leftCount = countNodes(root.left)
let rightCount = countNodes(root.right)
return leftCount + rightCount + 1
}
最小深度
func minDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 } // 如果根节点为空，返回 0
// 如果左子树为空且右子树不为空，返回右子树的最小深度加 1
if root.left == nil && root.right != nil {
return minDepth(root.right) + 1
}
// 如果右子树为空且左子树不为空，返回左子树的最小深度加 1
if root.right == nil && root.left != nil {
return minDepth(root.left) + 1
}
// 如果左右子树都不为空，返回左右子树最小深度的较小值加 1
if let leftDepth = root.left, let rightDepth = root.right {
return min(minDepth(leftDepth), minDepth(rightDepth)) + 1
}
// 如果左右子树都为空，说明当前节点是叶子节点，返回 1
return 1
}
3.二叉树的层序遍历、右视图、层平均值、是否为完全二叉树
层序遍历
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] } // 如果根节点为空，直接返回空数组
var result: [[Int]] = [] // 用于存储每一层的节点值
var queue: [TreeNode] = [root] // 使用队列进行层序遍历
while !queue.isEmpty {
let levelSize = queue.count // 当前层的节点数
var level: [Int] = [] // 存储当前层的节点值
for _ in 0..<levelSize {
let node = queue.removeFirst() // 取出队首节点
level.append(node.val) // 将节点值加入当前层数组
// 将当前节点的左、右子节点（如果存在）入队
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
result.append(level) // 将当前层数组加入结果数组
}
return result // 返回按层遍历的结果
}
右视图
func rightSideView(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] } // 如果根节点为空，返回空数组
var result = [Int]() // 存储每一层最右侧节点的值的数组
var queue = [TreeNode]() // 用于层序遍历的队列
queue.append(root) // 将根节点加入队列
while !queue.isEmpty {
let levelSize = queue.count // 当前层的节点数量
// 遍历当前层的所有节点
for _ in 0..<levelSize {
let node = queue.removeFirst() // 取出并移除队列中的第一个节点
// 将当前节点最右侧的值添加到结果数组中
if queue.isEmpty || (queue.first?.left == nil && queue.first?.right == nil) { // 判断是否为本层最右侧节点
result.append(node.val)
}
// 将当前节点的子节点加入队列
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
}
return result
}
层平均值
要计算二叉树每一层的平均值（即层平均值），你仍然需要执行层序遍历（广度优先遍历），但这次在遍历每一层时，你需要累加该层所有节点的值，并除以该层的节点数来得到平均值。
func averageOfLevels(_ root: TreeNode?) -> [Double] {
guard let root = root else { return [] } // 如果根节点为空，返回空数组
var result = [Double]() // 存储每一层平均值的数组
var queue = [TreeNode]() // 用于层序遍历的队列
queue.append(root) // 将根节点加入队列
while !queue.isEmpty {
let levelSize = queue.count // 当前层的节点数量
var levelSum = 0 // 当前层的节点值之和
// 遍历当前层的所有节点
for _ in 0..<levelSize {
let node = queue.removeFirst() // 取出并移除队列中的第一个节点
levelSum += node.val // 累加当前节点的值
// 将当前节点的子节点加入队列
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
// 计算当前层的平均值并添加到结果数组中
let average = Double(levelSum) / Double(levelSize)
result.append(average)
}
return result
}
完全二叉树
在二叉树中，完全二叉树是指除了最后一层外，每一层上的节点数都达到最大值，并且最后一层上的节点都靠左紧密排列的二叉树。要判断一个二叉树是否是完全二叉树，我们可以使用层序遍历（广度优先搜索）的方法，并利用一个标记位来记录是否遇到了空节点。
一旦我们遇到了一个空节点，我们就应该确保后续的节点都是空的，因为完全二叉树的特点是：如果某个节点为空，那么它后面所有的节点都应为空。
func isCompleteTree(_ root: TreeNode?) -> Bool {
guard let root = root else { return true } // 空树视为完全二叉树
var queue = [TreeNode]()
var encounteredNull = false // 标记是否遇到了空节点
queue.append(root)
while !queue.isEmpty {
let node = queue.removeFirst()
if node.left != nil {
if encounteredNull {
// 如果之前已经遇到了空节点，但当前节点还有左子节点，则不是完全二叉树
return false
}
queue.append(node.left!)
} else {
// 遇到了空节点，将 encounteredNull 标记为 true
encounteredNull = true
}
if node.right != nil {
if encounteredNull {
// 如果之前已经遇到了空节点，但当前节点还有右子节点，则不是完全二叉树
return false
}
queue.append(node.right!)
} else {
// 如果右子节点为空，并且之前没遇到过空节点，则 encounteredNull 依然为 false
// 无需额外操作，继续遍历
}
}
return true // 遍历完成，未违反完全二叉树的定义，则返回 true
}
满二叉树
满二叉树（Full Binary Tree）是一种特殊的二叉树，其中除了叶子节点外，每个节点都有两个子节点。换句话说，满二叉树的每一层都完全填满，并且所有叶子节点都在同一层。
要判断一个二叉树是否为满二叉树，我们可以使用递归的方法。在递归过程中，我们需要确保每个非叶子节点都有两个子节点，并且所有叶子节点都位于同一层（这通常通过遍历过程中记录的层数来判断）。然而，在实际应用中，我们往往不需要显式地检查叶子节点是否在同一层，因为如果我们能确保每个非叶子节点都有两个子节点，那么叶子节点自然会在同一层。
func isFullBinaryTree(_ root: TreeNode?) -> Bool {
guard let root = root else { return true } // 空树视为满二叉树
// 递归检查左右子树是否都是满二叉树，并且确保当前节点有两个子节点
return (root.left != nil && root.right != nil) && // 当前节点有两个子节点
isFullBinaryTree(root.left) && // 左子树是满二叉树
isFullBinaryTree(root.right) // 右子树是满二叉树
}
4.对称二叉树
要判断一个二叉树是否是对称的，可以采用递归的方法。对称二叉树意味着二叉树的左子树与右子树在结构上镜像对称，且每个节点的值都相等。
func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true } // 空树是对称的
return isMirror(root.left, root.right)
}
// 辅助函数，判断两棵树是否镜像对称
func isMirror(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
return (t1?.val == t2?.val) &&
isMirror(t1?.left, t2?.right) && // 注意这里是左右互换
isMirror(t1?.right, t2?.left)
}
