计算二叉树的高度

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

# 定义二叉树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 计算二叉树高度的函数
def tree_height(root):
    if not root:
        return 0
    left_height = tree_height(root.left)
    right_height = tree_height(root.right)
    return max(left_height, right_height) + 1

在这个函数中，如果当前节点为空，则返回 0；否则，分别计算左子树和右子树的高度，然后取两者的最大值加上 1 就是当前节点的高度。最终返回根节点的高度即可。

相关问题

后序非递归算法计算二叉树高度

二叉树高度的非递归算法可以通过层次遍历实现。下面是一种基于队列的算法：

1. 初始化一个空队列，并将根节点入队。
2. 初始化一个变量 height，并将其置为 0。
3. 循环执行以下步骤，直到队列为空：
a. 获取当前队列的长度，表示当前层的节点个数。
b. 遍历当前层的所有节点：
i. 将当前节点出队。
ii. 如果当前节点有左子节点，将其入队。
iii. 如果当前节点有右子节点，将其入队。
c. 增加 height 的值。
4. 返回 height 的值作为二叉树的高度。

这种非递归算法利用了队列的先进先出特性，每层的节点按照从左到右的顺序依次入队，从而实现了按层遍历。通过记录遍历的层数，最终得到二叉树的高度。

用c++写一个计算二叉树高度的代码

好的，以下是使用C语言编写计算二叉树高度的代码：

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

#define max(a, b) ((a) > (b) ? (a) : (b))

// 二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int maxDepth(struct TreeNode* root) {
    if (root == NULL) { // 根节点为空，二叉树高度为0
        return 0;
    }
    int leftDepth = maxDepth(root->left); // 计算左子树高度
    int rightDepth = maxDepth(root->right); // 计算右子树高度
    return max(leftDepth, rightDepth) + 1; // 返回左右子树高度的最大值并加上根节点高度
}

int main() {
    // 示例1
    //     3
    //    / \
    //   9  20
    //     /  \
    //    15   7
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 3;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 9;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 20;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 15;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 7;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    printf("二叉树高度：%d\n", maxDepth(root)); // 预期输出结果为3

    return 0;
}

也可以使用队列来进行层序遍历求解二叉树高度，具体实现不再赘述。