数据结构求二叉树高度

求二叉树的高度可以用递归的方法实现，具体的算法如下：

1. 如果树为空，返回 0
2. 否则，分别递归计算左子树和右子树的高度，取其中的较大值，并加上根节点的高度 1，即为整棵树的高度。

以下是 Python 代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root: TreeNode) -> int:
    if not root:
        return 0
    left_height = height(root.left)
    right_height = height(root.right)
    return max(left_height, right_height) + 1

其中，`TreeNode` 是二叉树的节点类，`height` 函数输入一个二叉树的根节点，返回二叉树的高度。

相关问题

数据结构写代码实现求二叉树的高度

在计算机科学中，二叉树的高度通常是指从根节点到最远叶子节点的最大路径长度。下面是使用递归方式在Python中实现计算二叉树高度的一个简单示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if root is None:  # 如果根节点为空，高度为0
        return 0
    else:
        left_height = height(root.left)  # 左子树的高度
        right_height = height(root.right)  # 右子树的高度
        return max(left_height, right_height) + 1  # 返回根节点、左右子树高度较大值加1

# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

# 调用函数计算高度
tree_height = height(root)
print("二叉树的高度是:", tree_height)

在这个例子中，`height` 函数首先检查根节点是否为空，如果为空则返回0。接着分别计算左子树和右子树的高度，并取较大的那个值加1作为当前节点的高度。这样层层递归直到找到空节点。

层次遍历求二叉树高度C语言

层次遍历（BFS，即广度优先搜索）通常使用队列数据结构来实现二叉树的高度查找。这里是一个简单的C语言代码示例，用于计算给定二叉树的高度：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int height(TreeNode* root) {
    if (root == NULL) { // 空树的高度为0
        return 0;
    }
    
    int level = 0; // 当前层数
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size(); // 当前层的节点数量
        level++;
        
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left != NULL) {
                q.push(node->left);
            }
            if (node->right != NULL) {
                q.push(node->right);
            }
        }
    }

    return level;
}

// 主函数测试
int main() {
    // 初始化一个二叉树实例并替换此处代码
    TreeNode* root = ...;

    int treeHeight = height(root);
    printf("二叉树的高度为: %d\n", treeHeight);
    return 0;
}

这个程序首先检查根节点是否为空，然后创建一个队列并将根节点放入。接着进入循环，直到队列为空。每次循环，都会计算出当前层的节点数量，然后访问每个节点的左右子节点，并将其加入队列。当队列为空时，说明已经遍历完所有层级，返回此时的层数即为树的高度。