编写一个递归函数height，传入参数为二叉树根结点的指针root，计算二叉树的高度。 要求： （1）用自然语言简要描述算法思想； （2）用类C或C++语言形式的伪代码描述算法步骤； （3）分析算法的时间复杂度。

算法思想：递归遍历二叉树，每次递归返回当前节点的子树高度加1，直到遍历到叶子节点，返回0。

伪代码：

int height(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return max(leftHeight, rightHeight) + 1;
}

时间复杂度：每个节点只会被遍历一次，所以时间复杂度为O(n)，其中n为节点数。

相关问题

编写一个递归函数height,传入参数为二叉树根节点的指针root计算二叉树高度

下面是C++代码实现：

int height(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return max(left_height, right_height) + 1;
}

递归函数的核心思想是求出左右子树的高度，然后取较大值加1即可。如果根节点为空，返回0。

请使用二叉树的先序遍历算法，统计二叉树中叶子结点的个数(假设二叉 树已经使用链式存储，根结点的指针为Btree *root) 。不需要函数模板。 函数原型: void leaf count(Btree *root,int &k) 其中指针root指向二叉树的根结点，参数k为统计叶子结点数。

下面是二叉树先序遍历算法，统计叶子结点的个数的代码：

struct Btree{
    int val;
    Btree *left, *right;
};

void leafCount(Btree *root, int &k){
    if(root == NULL){
        return;
    }
    if(root->left == NULL && root->right == NULL){
        k++;
    }
    leafCount(root->left, k);
    leafCount(root->right, k);
}

其中，参数 `root` 指向二叉树的根结点，参数 `k` 用来统计叶子结点数。当 `root` 为空时，直接返回；当 `root` 的左右子树都为空时，说明 `root` 是叶子结点，统计器 `k` 加 1；否则，递归遍历左右子树。

使用时，可以将 `k` 初始化为 0，再调用 `leafCount` 函数，最后输出 `k` 即可得到叶子结点数。