二叉树的叶子结点深度
时间: 2023-11-24 22:07:27 浏览: 72
二叉树叶子结点个数计算.doc
5星 · 资源好评率100%
二叉树的叶子结点深度是指所有叶子节点的深度之和,可以使用递归的方法遍历整个二叉树,找到所有的叶子节点,并计算它们的深度之和。
具体实现如下:
```c++
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int sumOfLeafNodesDepth(TreeNode* root, int depth) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) { // 当前节点是叶子节点
return depth;
}
int leftDepth = sumOfLeafNodesDepth(root->left, depth + 1); // 递归遍历左子树
int rightDepth = sumOfLeafNodesDepth(root->right, depth + 1); // 递归遍历右子树
return leftDepth + rightDepth; // 返回左右子树深度之和
}
```
上述代码中,我们定义了一个 `sumOfLeafNodesDepth` 函数,它的输入参数是二叉树的根节点指针和当前节点的深度。如果根节点为空,说明二叉树为空树,直接返回0。如果当前节点是叶子节点(即左右子节点都为空),返回当前节点的深度。然后,再递归遍历左子树和右子树,将左右子树的深度之和返回即可。
需要注意的是,递归遍历左右子树时,需要将当前节点的深度加1传递给递归函数。
阅读全文