给定一棵用二叉链表表示的二叉树，其根指针为 root，试写出求二叉树的深度的法

方法一：递归法

递归地求解左子树的深度和右子树的深度，然后取最大值加1即为整棵树的深度。

示例代码：

int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}

方法二: 迭代法

采用层序遍历的方式遍历二叉树，记录深度，直到遍历到最后一层为止，即可得到二叉树的深度。

示例代码：

int maxDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q{{root}};
int depth = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
auto node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
depth++;
}
return depth;
}

相关问题

给定一棵用二叉链表表示的二叉树，其根指针为 root，试写出求二叉树的深度的法。

您好，根据您的描述，您想问如何求二叉树的深度。下面是求二叉树深度的C++代码。请注意，此代码仅适用于用二叉链表表示的二叉树。

int getDepth(TreeNode* root) {
    if(root == NULL) { // 当前节点为空，深度为0
        return 0;
    }
    int leftDepth = getDepth(root->left); // 递归求左子树深度
    int rightDepth = getDepth(root->right); // 递归求右子树深度
    return max(leftDepth, rightDepth) + 1; // 返回左右子树深度的最大值加1
}

以上代码中，`TreeNode`是表示二叉树节点的结构体，包含左右两个指针和节点值等信息。函数`getDepth`首先判断当前节点是否为空，若为空，则深度为0。否则，分别递归求出左子树的深度和右子树的深度，并返回二者的最大值加1，即为整棵二叉树的深度。

希望能够帮到您，如有疑问请随时提出。

给定一棵用二叉链表表示的二叉树，其根指针为 root，试写出求二叉树结点的数的算法。

当您输入 "给定一棵用二叉链表表示的二叉树，其根指针为 root，试写出求二叉树结点的数的算法。" 时，我的ChitGPT AI将给予以下回答：

可以使用递归的方式来求解二叉树结点的数。具体地，对于一棵二叉树，其结点数等于其左子树的结点数加上右子树的结点数再加上1（根结点）。

因此，可以定义一个递归函数countNodes，以某个结点为根的子树作为参数，返回该子树中的结点数。具体实现方式如下：

int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}

其中，当给出的子树为空时，其结点数为0；否则，使用递归计算其左子树和右子树的结点数，并相加1（根结点数），即可得到该子树的结点数。

希望以上回答能够帮助您。