C++算法（10）：二叉树的高度与深度，（C++代码实战）

引言

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

---

定义与区别

属性	定义	计算方式
深度	从根节点到该节点的边数	根节点深度为0
高度	从该节点到最远叶子节点的边数	叶子节点高度为0

核心区别：

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

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

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

---

示例与表格

以下图二叉树为例：

       A/   \B     C/       \D         E

各节点的属性如下表：

节点	深度	高度
A	0	2
B	1	1
C	1	1
D	2	0
E	2	0

---

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; // 空节点高度为-1return 1 + max(height(root->left), height(root->right));
}

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

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

注意事项

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

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

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

2. 应用场景：

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

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

---

总结

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

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

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