编写一个递归函数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。

相关问题

编写一个递归函数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为节点数。

写一个递归函数计算二叉树高度

假设二叉树的节点结构如下：

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

其中`height`函数的参数`root`表示根节点，返回值是树的高度。如果根节点为空，则返回0；否则，分别计算左右子树的高度，并取最大值，加1即为整棵树的高度。