怎么看二叉树的高度

二叉树是一种非常重要的数据结构，在计算机科学中应用广泛。在数据结构中，二叉树是由节点组成的树状结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。对于二叉树来说，其高度是从根节点到最深节点的路径的长度。在本文中，将会从多个角度分析如何看二叉树的高度。

1. 根据定义计算二叉树的高度

二叉树的高度可以根据其定义来计算，也就是从根节点开始，递归计算左子树和右子树的高度，然后返回较大的值。具体步骤如下：

- 首先判断树是否为空，如果为空则返回0。

- 否则，递归计算左子树的高度。

- 然后递归计算右子树的高度。

- 取左子树和右子树高度的最大值。

- 最后加1，表示根节点的高度。

- 返回结果。

下面是一个示例代码：

```

int height(Node* root) {

// 如果根节点为空，直接返回0

if (root == NULL) {

return 0;

}

// 计算左子树的高度

int left_height = height(root->left);

// 计算右子树的高度

int right_height = height(root->right);

// 取左右子树高度的最大值

int max_height = max(left_height, right_height);

// 加1，表示根节点的高度

return max_height + 1;

}

```

2. 使用队列进行层序遍历

另一种计算二叉树高度的方法是使用队列进行层序遍历。层序遍历是一种广度优先搜索，它按照树的层次从上到下依次访问树中的每个节点。在层序遍历中，我们可以计算每一层的宽度，然后累加得到树的高度。

具体步骤如下：

- 如果根节点为空，直接返回0。

- 否则，创建一个队列，并将根节点放入队列中。

- 创建一个变量height，表示当前遍历的层数，初始值为0。

- 在循环中，首先记录当前队列的大小，然后将队列中的所有节点依次出队，并将它们的子节点入队。在此过程中，累加层数。

- 遍历完成后，返回height。

下面是一个示例代码：

```

int height(Node* root) {

// 如果根节点为空，直接返回0

if (root == NULL) {

return 0;

}

// 创建一个队列

queue q;

// 将根节点入队

q.push(root);

// 初始化height为0

int height = 0;

// 循环遍历队列中的节点

while (!q.empty()) {

// 记录当前层的节点数

int size = q.size();

// 将当前层的所有节点依次出队，并将它们的子节点入队

for (int i = 0; i < size; i++) {

Node* node = q.front();

q.pop();

if (node->left != NULL) {

q.push(node->left);

}

if (node->right != NULL) {

q.push(node->right);

}

}

// 累加层数

height++;

}

// 返回层数

return height;

}

```

3. 分治法计算二叉树的高度

分治法是一种常用的求解复杂问题的算法，它将问题分解成多个子问题，然后通过合并子问题的解来得到原问题的解。对于二叉树的高度问题，我们可以将其分解为左右子树的高度，然后将左右子树的高度求最大值并加1，得到根节点的高度。

具体步骤如下：

- 如果根节点为空，直接返回0。

- 否则，递归计算左子树的高度。

- 递归计算右子树的高度。

- 取左子树和右子树高度的最大值。

- 最后加1，表示根节点的高度。

- 返回结果。

下面是一个示例代码：

```

int height(Node* root) {

// 如果根节点为空，直接返回0

if (root == NULL) {

return 0;

}

// 递归计算左子树的高度

int left_height = height(root->left);

// 递归计算右子树的高度

int right_height = height(root->right);

// 取左右子树高度的最大值

int max_height = max(left_height, right_height);

// 加1，表示根节点的高度

return max_height + 1;

}

```