怎么用递归求解树的节点数量
时间: 2023-07-11 08:44:38 浏览: 56
求解树节点数量的递归算法可以如下实现:
1. 如果树为空,节点数量为0,返回0。
2. 否则,节点数量为1 + 左子树节点数量 + 右子树节点数量。
3. 分别递归求解左子树节点数量和右子树节点数量。
4. 将左子树节点数量和右子树节点数量加起来作为当前节点的节点数量。
5. 返回当前节点的节点数量。
下面是一个示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def countNodes(root: TreeNode) -> int:
if not root:
return 0
left_count = countNodes(root.left)
right_count = countNodes(root.right)
return 1 + left_count + right_count
```
这个函数接受一个树的根节点作为参数,返回该树的节点数量。函数通过递归调用左右子树的节点数量来求解当前节点的节点数量,最终返回整个树的节点数量。
相关问题
怎么用递归求解树的节点数量用Java语法
使用递归算法求解树的节点数量的Java代码示例:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = countNodes(root.left);
int rightCount = countNodes(root.right);
return 1 + leftCount + rightCount;
}
```
这个函数接受一个树的根节点作为参数,返回该树的节点数量。函数通过递归调用左右子树的节点数量来求解当前节点的节点数量,最终返回整个树的节点数量。
Java 如何求解树所有节点的深度
要求解一棵树所有节点的深度,可以使用递归方法。
首先,需要定义一个递归函数,用于计算树的深度。该函数的输入参数为当前节点和当前深度,输出为当前节点的深度。
然后,在递归函数中,需要遍历当前节点的所有子节点,并计算每个子节点的深度。遍历完所有子节点后,返回子节点深度的最大值加上 1,即为当前节点的深度。
最后,在主函数中,调用递归函数,并传入根节点和深度为 0 的初始值,得到树所有节点的深度。
下面是 Java 代码示例:
```java
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
public class TreeDepth {
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int maxChildDepth = 0;
for (TreeNode child : root.children) {
maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
}
return maxChildDepth + 1;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.children.add(new TreeNode(2));
root.children.add(new TreeNode(3));
root.children.get(0).children.add(new TreeNode(4));
root.children.get(0).children.add(new TreeNode(5));
root.children.get(1).children.add(new TreeNode(6));
int depth = maxDepth(root);
System.out.println("The depth of the tree is: " + depth);
}
}
```
输出结果:
```
The depth of the tree is: 3
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)