二叉树求高度

### 二叉树高度计算的算法实现 #### 理论基础 二叉树的高度定义为从根节点到最远叶节点的最长路径上的边数[^4]。对于任意给定的二叉树，可以通过递归方法来计算其高度。具体而言，若当前节点为空，则返回0；否则分别递归计算左子树和右子树的高度，并取两者中的最大值再加1作为当前节点的高度。 --- #### Python 实现 以下是基于递归的 Python 实现： ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def get_binary_tree_height(root): if root is None: # 如果节点为空，返回0 return 0 # 分别获取左右子树的高度 left_height = get_binary_tree_height(root.left) right_height = get_binary_tree_height(root.right) # 返回左右子树高度的最大值并加1 return max(left_height, right_height) + 1 ``` 此代码片段展示了如何通过递归函数 `get_binary_tree_height` 来计算二叉树的高度[^2]。 --- #### C++ 实现 下面是使用 C++ 的一种实现方式： ```cpp #include <iostream> using namespace std; struct BinaryTreeNode { int data; BinaryTreeNode* left; BinaryTreeNode* right; }; // 定义求高度的函数 int GetBinaryTreeHeight(BinaryTreeNode* node) { if (node == nullptr) { // 节点为空时返回0 return 0; } int leftHeight = GetBinaryTreeHeight(node->left); // 左子树高度 int rightHeight = GetBinaryTreeHeight(node->right); // 右子树高度 return max(leftHeight, rightHeight) + 1; // 返回较大者加1 } // 创建测试用例 BinaryTreeNode* CreateTestTree() { BinaryTreeNode* root = new BinaryTreeNode(); root->data = 1; root->left = new BinaryTreeNode(); root->left->data = 2; root->right = new BinaryTreeNode(); root->right->data = 3; root->left->left = new BinaryTreeNode(); root->left->left->data = 4; return root; } int main() { BinaryTreeNode* tree = CreateTestTree(); cout << "The height of the binary tree is: " << GetBinaryTreeHeight(tree) << endl; return 0; } ``` 这段代码提供了完整的结构体定义以及递归调用来计算二叉树高度的功能[^5]。 --- #### Java 实现 下面是一个标准的 Java 版本实现： ```java public class BinaryTreeHeight { static class TreeNode { int val; TreeNode left, right; public TreeNode(int item) { this.val = item; this.left = this.right = null; } } public static int getHeight(TreeNode root) { if (root == null) { // 当前节点为空时返回0 return 0; } int leftHeight = getHeight(root.left); // 获取左子树高度 int rightHeight = getHeight(root.right); // 获取右子树高度 return Math.max(leftHeight, rightHeight) + 1; // 返回两者的较大值加1 } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); System.out.println("Height of the binary tree is: " + getHeight(root)); } } ``` Java 中同样采用了递归来解决这个问题[^2]。 --- ### 复杂度分析 时间复杂度：O(n)，其中 n 是二叉树中节点的数量。这是因为每个节点都会被访问一次。 空间复杂度：取决于递归栈的空间消耗，在最坏情况下（退化成链表的情况），空间复杂度为 O(n)[^3]。 ---