统计二叉树中具有度为1的结点数目 分数 5
时间: 2024-03-16 12:42:56 浏览: 72
对于一棵二叉树,度为1的结点有且仅有两种情况:
1. 节点的左子树或右子树为空,但它的另一颗子树非空
2. 节点的左子树和右子树都非空,但它本身的度为1
因此,对于一颗二叉树,统计度为1的结点数目的方法如下:
1. 对于空树,度为1的结点数目为0
2. 对于非空树,分别统计左子树和右子树中度为1的结点数目
3. 如果当前节点的左子树或右子树为空,但它的另一颗子树非空,则当前节点的度为1,将结果加1
4. 如果当前节点的左子树和右子树都非空,但它本身的度为1,则当前节点的度为1,将结果加1
5. 最后返回左子树、右子树和当前节点的度为1的结点数目之和
下面是Java代码实现:
```java
public int countDegree1Nodes(TreeNode root) {
if (root == null) {
return 0;
}
int left = countDegree1Nodes(root.left);
int right = countDegree1Nodes(root.right);
int degree = (root.left == null && root.right != null) || (root.left != null && root.right == null) || (root.left != null && root.right != null && root.degree() == 1) ? 1 : 0;
return left + right + degree;
}
```
阅读全文