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

编写一个递归函数，检查二叉树是否为平衡二叉树

在Python中，我们可以编写一个名为`is_balanced`的递归函数来检查一个给定的二叉树是否是平衡二叉树。平衡二叉树是指每个节点的左右子树的高度差不超过1的二叉搜索树。下面是这个函数的基本实现：

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

def height(node):
    if node is None:
        return 0
    else:
        # 计算左子树和右子树的高度，取较大值加1作为当前节点的高度
        left_height = height(node.left)
        right_height = height(node.right)
        return max(left_height, right_height) + 1

def is_balanced(root):
    if root is None:
        return True
    # 获取根节点的高度
    height_diff = abs(height(root.left) - height(root.right))
    
    # 如果高度差超过1，说明不是平衡二叉树
    if height_diff > 1:
        return False
    else:
        # 对左右子树分别递归检查
        return is_balanced(root.left) and is_balanced(root.right)

# 测试用例
# 构建一个不平衡的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(is_balanced(root))  # 输出：False

# 构建一个平衡的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

print(is_balanced(root))  # 输出：True