引言

在二叉树的相关算法中，高度（Height）和深度（Depth）是两个容易混淆的概念。本文通过示例和代码实现，帮助读者清晰区分二者的区别。

定义与区别

核心区别：

• 深度是自上而下从根节点到当前节点的路径长度。

• 高度是自下而上从当前节点到最远叶子节点的路径长度。

• 树的高度等于根节点的高度，也等于树的最大深度。

示例与表格

以下图二叉树为例：

       A
     /   \
    B     C
   /       \
  D         E

各节点的属性如下表：

C++实现

1. 树节点定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 计算高度（递归）

int height(TreeNode* root) {
    if (!root) return -1; // 空节点高度为-1
    return 1 + max(height(root->left), height(root->right));
}

3. 计算深度（递归搜索）

int depth(TreeNode* root, TreeNode* target) {
    if (!root) return -1; // 未找到目标
    if (root == target) return 0; // 找到目标，深度为0
    int left = depth(root->left, target);
    if (left != -1) return left + 1; // 左子树中找到，深度+1
    int right = depth(root->right, target);
    return (right != -1) ? right + 1 : -1;
}

注意事项

1. 定义差异：某些场景中，深度和高度的计算可能基于节点数而非边数。例如：

   • 根节点深度为1，叶子节点高度为1。

   • 此时树的高度等于最大深度，需调整代码逻辑。

2. 应用场景：

   • 高度常用于平衡二叉树判断（如AVL树）。

   • 深度常用于路径问题（如最大深度）。

总结

• 高度关注当前节点到叶子的最长路径。

• 深度关注根节点到当前节点的路径。

• 代码实现需根据具体定义调整边界条件。