5-2 计算二叉树深度 分数 8 作者 王东 单位 贵州师范学院 计算二叉树深度。 #incl
时间: 2023-09-06 12:00:51 浏览: 135
计算二叉树的深度可以使用递归的方法来解决。首先,判断二叉树是否为空,如果为空则深度为0。如果不为空,则可以计算左子树的深度和右子树的深度,并取二者中较大的值加上1作为整个二叉树的深度。
具体步骤如下:
1. 判断二叉树是否为空。
- 如果为空,则返回深度为0。
- 如果不为空,则继续下一步。
2. 递归计算左子树的深度。
- 将二叉树的左子树作为根节点进行递归计算。
- 将递归返回的深度存储在一个变量中。
3. 递归计算右子树的深度。
- 将二叉树的右子树作为根节点进行递归计算。
- 将递归返回的深度存储在一个变量中。
4. 取左子树深度和右子树深度的最大值,并加上1作为整个二叉树的深度。
- 比较左子树深度和右子树深度的大小,取较大值。
- 将较大值加上1,作为整个二叉树的深度。
5. 返回整个二叉树的深度。
这样就能够计算出给定二叉树的深度。通过递归的方式,我们可以对二叉树的每个子树进行深度的计算,并最终得到整个二叉树的深度。
相关问题
6-6 判断两棵二叉树是否同构(递归法) 分数 10 作者 王东 单位 贵州师范学院 判断
好的,你的问题是如何判断两棵二叉树是否同构(递归法)。
同构指的是两棵二叉树的结构相同,但是节点的值可以不同。这里给出递归法的代码实现:
```python
def is_isomorphic(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
return (is_isomorphic(root1.left, root2.left) and
is_isomorphic(root1.right, root2.right)) or \
(is_isomorphic(root1.left, root2.right) and
is_isomorphic(root1.right, root2.left))
```
在递归过程中,首先判断两个根节点是否为空,如果都为空,则返回 True。如果其中一个为空,则返回 False。接下来判断两个根节点的值是否相同,如果不相同,则返回 False。
如果两个根节点的值相同,那么就需要递归判断左子树和右子树是否同构,或者判断左子树和右子树是否交叉同构。只有两者之一成立,才返回 True,否则返回 False。
这样,就完成了判断两棵二叉树是否同构的递归实现。
计算二叉树的深度
好的,计算二叉树的深度可以使用递归的方法。对于一棵二叉树,它的深度等于左子树的深度和右子树的深度的较大值加1。以下是计算二叉树深度的示例代码(假设二叉树已经存在,且每个节点包含一个整数值和左、右子节点指针):
```
int max_depth(node* root) {
if (root == nullptr) {
return 0;
}
int left_depth = max_depth(root->left); // 计算左子树的深度
int right_depth = max_depth(root->right); // 计算右子树的深度
return max(left_depth, right_depth) + 1; // 返回左右子树深度的较大值加1
}
```
调用该函数并传入二叉树的根节点,即可得到二叉树的深度。
相关推荐
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)