EB2-计算二叉树深度

问题分析

二叉树深度（高度）定义： - 空树的深度为 0 - 非空树的深度 = 1 + max(左子树深度, 右子树深度) - 从根结点到最远叶子结点的最长路径上的结点数

[[#3. 查找最大深度路径]]

方法一：递归计算型（后序遍历）

代码实现

/**
 * 计算二叉树最大深度（高度）- 计算型实现
 * 参数：p - 二叉树根结点
 * 返回值：树的深度
 */
int func(BiTree p) {
    // 递归终止条件：空树深度为0
    if (p == NULL) {
        return 0;
    } else {
        // 递归计算左子树深度
        int L1 = func(p->lchild);

        // 递归计算右子树深度
        int L2 = func(p->rchild);

        // 当前树深度 = 1 + max(左子树深度, 右子树深度)
        return (L1 > L2 ? L1 : L2) + 1;
    }
}

/**
 * 更清晰的版本
 */
int maxDepth(BiTree root) {
    // 基础情况：空树
    if (root == NULL) {
        return 0;
    }

    // 递归计算左右子树深度
    int leftDepth = maxDepth(root->lchild);
    int rightDepth = maxDepth(root->rchild);

    // 返回较大深度 + 1（当前结点）
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

执行过程图解

// 二叉树示例：
//       1
//      / \
//     2   3
//    / \
//   4   5
//      /
//     6

// 递归执行过程：
// maxDepth(1)
// ├── maxDepth(2)
// │   ├── maxDepth(4) → 1
// │   ├── maxDepth(5)
// │   │   ├── maxDepth(6) → 1
// │   │   └── maxDepth(NULL) → 0
// │   │   → max(1,0)+1 = 2
// │   └── max(1,2)+1 = 3
// ├── maxDepth(3) → 1
// └── max(3,1)+1 = 4

// 结果：最大深度为4

方法二：操作型（前序遍历 + 回溯）

代码实现

/**
 * 计算二叉树最大深度（高度）- 操作型实现
 * 参数说明：
 * p - 当前遍历的结点
 * L - 当前路径长度（引用传递）
 * max_L - 最大深度（引用传递）
 */
void func(BiTree p, int *L, int *max_L) {
    // 递归终止条件：当前结点不为空
    if (p != NULL) {
        // 进入当前结点：路径长度加1
        ++(*L);

        // 更新最大深度
        if (*L >= *max_L) {
            *max_L = *L;
        }

        // 递归遍历左子树
        func(p->lchild, L, max_L);

        // 递归遍历右子树
        func(p->rchild, L, max_L);

        // 回溯：离开当前结点，路径长度减1
        --(*L);
    }
}

/**
 * 操作型主函数包装
 */
int maxDepth_Operational(BiTree root) {
    int currentDepth = 0;  // 当前路径深度
    int maxDepth = 0;      // 最大深度

    func(root, &currentDepth, &maxDepth);

    return maxDepth;
}

执行过程图解

// 二叉树示例：
//       1
//      / \
//     2   3
//    / \
//   4   5
//      /
//     6

// 遍历执行过程（显示L和max_L的变化）：
// 访问1：L=1, max_L=1
// ├── 访问2：L=2, max_L=2
// │   ├── 访问4：L=3, max_L=3
// │   │   ← 回溯：L=2
// │   ├── 访问5：L=3, max_L=3
// │   │   ├── 访问6：L=4, max_L=4
// │   │   │   ← 回溯：L=3
// │   │   ← 回溯：L=2
// │   ← 回溯：L=1
// ├── 访问3：L=2, max_L=4
// │   ← 回溯：L=1
// ← 回溯：L=0

// 结果：最大深度为4

复杂度分析

时间复杂度

两种方法对比

• 方法一（计算型）：O(N) - 每个结点访问一次
• 方法二（操作型）：O(N) - 每个结点访问一次

详细分析

设树中共有N个结点：
- 每个结点都需要被访问一次
- 每次访问进行常数时间操作
- 总时间复杂度：O(N)

空间复杂度

方法一（计算型）

• 递归栈空间：O(h) - h为树的高度
• 最好情况（完全平衡）：O(log N)
• 最坏情况（退化为链表）：O(N)
• 总体空间复杂度：O(N)

方法二（操作型）

• 递归栈空间：O(h) - h为树的高度
• 额外变量：O(1) - 两个整型指针
• 总体空间复杂度：O(N)

两种方法对比

特性	计算型	操作型
核心思想	后序遍历，自底向上计算	前序遍历，自顶向下追踪
返回方式	直接返回计算结果	通过参数传递结果
实现复杂度	简单直观	稍复杂
空间使用	较少额外变量	需要维护路径信息
执行效率	略高	略低
适用场景	纯计算	需要路径信息

优化版本

1. 非递归实现（层序遍历）

/**
 * 非递归实现：使用层序遍历计算深度
 */
int maxDepth_Iterative(BiTree root) {
    if (root == NULL) return 0;

    // 使用队列进行层序遍历
    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int depth = 0;

    // 根结点入队
    queue[rear++] = root;

    while (front < rear) {
        int levelSize = rear - front;  // 当前层的结点数
        depth++;  // 深度加1

        // 处理当前层的所有结点
        for (int i = 0; i < levelSize; i++) {
            BiTree node = queue[front++];

            // 将子结点加入队列
            if (node->lchild != NULL) {
                queue[rear++] = node->lchild;
            }
            if (node->rchild != NULL) {
                queue[rear++] = node->rchild;
            }
        }
    }

    return depth;
}

实际应用场景

1. 平衡性检查

/**
 * 检查二叉树是否平衡
 */
bool isBalanced(BiTree root) {
    return checkBalance(root) != -1;
}

int checkBalance(BiTree root) {
    if (root == NULL) return 0;

    int leftHeight = checkBalance(root->lchild);
    if (leftHeight == -1) return -1;

    int rightHeight = checkBalance(root->rchild);
    if (rightHeight == -1) return -1;

    if (abs(leftHeight - rightHeight) > 1) {
        return -1;  // 不平衡
    }

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

2. 内存分配优化

/**
 * 根据树深度预分配栈空间
 */
void processTreeWithPreallocatedStack(BiTree root) {
    int depth = maxDepth(root);
    // 根据深度预分配适当大小的栈
    int* stack = (int*)malloc(depth * sizeof(int));
    // ... 处理逻辑
    free(stack);
}

3. 系统资源管理

/**
 * 根据树深度设置递归限制
 */
void setRecursionLimit(BiTree configTree) {
    int treeDepth = maxDepth(configTree);
    // 设置系统递归深度限制
    setSystemRecursionLimit(treeDepth + 10);  // 留有余量
}

相关算法扩展

1. 计算最小深度

/**
 * 计算二叉树最小深度
 */
int minDepth(BiTree root) {
    if (root == NULL) return 0;

    // 特殊情况：只有右子树或只有左子树
    if (root->lchild == NULL) {
        return minDepth(root->rchild) + 1;
    }
    if (root->rchild == NULL) {
        return minDepth(root->lchild) + 1;
    }

    // 一般情况：左右子树都存在
    int leftMin = minDepth(root->lchild);
    int rightMin = minDepth(root->rchild);

    return (leftMin < rightMin ? leftMin : rightMin) + 1;
}

2. 计算每层结点数

/**
 * 计算每层的结点数
 */
void getLevelCount(BiTree root, int level, int count[]) {
    if (root == NULL) return;

    count[level]++;
    getLevelCount(root->lchild, level + 1, count);
    getLevelCount(root->rchild, level + 1, count);
}

int getMaxWidth(BiTree root) {
    if (root == NULL) return 0;

    int depth = maxDepth(root);
    int* levelCount = (int*)calloc(depth, sizeof(int));

    getLevelCount(root, 0, levelCount);

    int maxWidth = 0;
    for (int i = 0; i < depth; i++) {
        if (levelCount[i] > maxWidth) {
            maxWidth = levelCount[i];
        }
    }

    free(levelCount);
    return maxWidth;
}

3. 查找最大深度路径

/**
 * 在二叉树中查找一条从根到叶子的路径，其长度等于给定的最大深度 maxDepth。
 * 若存在这样的路径，path 数组将保存该路径上的节点值（前 maxDepth 个元素有效）。
 *
 * @param root      当前遍历的树节点
 * @param path      存储从根到当前节点的路径
 * @param pathLen   当前路径的长度（已存储的节点数）
 * @param maxDepth  目标深度（最大深度）
 * @return          是否找到了一条长度为 maxDepth 的根到叶子路径
 */
bool findMaxDepthPath(BiTree root, int path[], int pathLen, int maxDepth) {
    // 空节点：无法构成路径
    if (root == NULL) {
        return false;
    }

    // 将当前节点加入路径
    path[pathLen] = root->data;

    // 判断是否为叶子节点 且 路径长度正好等于最大深度
    if (root->lchild == NULL && root->rchild == NULL && pathLen + 1 == maxDepth) {
        return true;  // 找到目标路径
    }

    // 递归搜索左子树和右子树
    // 只要任意一侧找到符合条件的路径，即成功
    bool foundInLeft  = findMaxDepthPath(root->lchild, path, pathLen + 1, maxDepth);
    bool foundInRight = findMaxDepthPath(root->rchild, path, pathLen + 1, maxDepth);

    return foundInLeft || foundInRight;
}

理论扩展

1. 数学性质分析

对于N个结点的二叉树：
- 最小深度：⌊log₂N⌋ + 1（完全二叉树）
- 最大深度：N（退化为链表）

深度与结点数的关系：
- 完全二叉树：深度 ≈ log₂N
- 平衡二叉树：深度 = O(log N)
- 普通二叉树：深度 = O(N)

2. 在不同树结构中的应用

// AVL树深度保证
int avlMaxDepth(BiTree root) {
    // AVL树的高度保证：h < 1.44 * log₂(n+2) - 0.328
    return maxDepth(root);  // 实际深度仍需计算
}

// 红黑树深度保证
int rbMaxDepth(BiTree root) {
    // 红黑树性质：从根到叶子的最长路径不超过最短路径的2倍
    return maxDepth(root);
}

3. 并行化处理

/**
 * 并行计算左右子树深度（概念性实现）
 */
int maxDepth_Parallel(BiTree root) {
    if (root == NULL) return 0;

    int leftDepth, rightDepth;

    // 并行计算左右子树深度
    #pragma omp parallel sections
    {
        #pragma omp section
        leftDepth = maxDepth(root->lchild);

        #pragma omp section
        rightDepth = maxDepth(root->rchild);
    }

    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

总结

两种计算二叉树最大深度的方法各有特点：

计算型方法（推荐）

• 优势：实现简洁，效率高，易于理解
• 适用：大多数场景下的首选方法
• 思想：分治法，自底向上计算

操作型方法

• 优势：可以获取遍历路径信息
• 适用：需要路径追踪的场景
• 思想：回溯法，自顶向下追踪

核心要点

1. 理解递归本质：深度 = 1 + max(左子树深度, 右子树深度)
2. 掌握边界处理：空树深度为0
3. 分析复杂度：时间O(N)，空间O(h)

这个算法体现了分治思想和递归技巧的完美结合，是树算法中的基础且重要的问题。通过对比学习两种实现方式，可以更好地理解不同算法设计思路的优劣。