pta 统计二叉树度为2的结点个数

### 如何在二叉树中统计度为2的结点个数

为了计算二叉树中度为2的结点数量，可以通过递归遍历整棵树来实现。对于每一个访问到的结点，如果该结点既有左子树也有右子树，则认为这是一个度为2的结点。

下面是一个C++版本的具体实现方式：

int countDegreeTwoNodes(BiTree T) {
    if (!T) return 0;
    
    // 如果当前节点有两个孩子，则返回1加上左右孩子的结果
    if (T->lchild && T->rchild) {
        return 1 + countDegreeTwoNodes(T->lchild) + countDegreeTwoNodes(T->rchild);
    }
    
    // 否则只继续向下搜索其存在的那个分支
    else {
        return countDegreeTwoNodes(T->lchild) + countDegreeTwoNodes(T->rchild);
    }
}

此代码片段展示了如何通过递归来解决这个问题[^1]。当遇到一个拥有两个非空子节点的情况时，就增加计数值；而对于只有一个或无任何子节点的情形，则不计入并继续探索其他可能存在的路径直到遍历完整棵二叉树为止。

此外，在某些情况下还可以采用迭代的方式来进行广度优先搜索（BFS），但这通常会涉及到额外的数据结构比如队列的应用，并且相对复杂一些。因此上述基于深度优先搜索（DFS）的方法更为简洁直观[^2]。

相关问题

统计二叉树度为1的结点个数pta

### 如何在二叉树中计算度为1的节点数量

为了统计二叉树中具有度为1的结点数目，可以采用遍历方法来逐个检查每个结点的孩子情况。如果某个结点仅有一个孩子（即左子结点或右子结点存在），则认为该结点的度为1。

下面是一个Python函数实现，用于计算给定二叉树中度为1的结点的数量：

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def count_degree_one_nodes(root):
    if not root:
        return 0
    
    stack = [root]
    degree_one_count = 0

    while stack:
        node = stack.pop()
        
        # Check if the current node has exactly one child.
        if (node.left and not node.right) or (not node.left and node.right):
            degree_one_count += 1
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return f"num: {degree_one_count}"


# Example usage based on input pattern provided
input_samples = ["HDA**C*B**GF*E***", "A*B*C*D*E*F**"]
for sample in input_samples:
    # Assuming a function `build_tree_from_string` exists to build tree from string representation
    tree_root = build_tree_from_string(sample)  
    result = count_degree_one_nodes(tree_root)
    print(result)

此代码定义了一个辅助类`TreeNode`表示二叉树中的单个结点，并实现了`count_degree_one_nodes`函数来进行广度优先搜索(BFS)，通过栈结构迭代处理每一个结点并判断其是否有且只有一个子结点[^1]。

pta 6-2 统计二叉树叶子结点个数

PTA（Problem Translation Agreement）题目编号6-2通常是指一道算法题，它涉及到统计一棵给定的二叉树中叶子节点的数量。在二叉树结构中，叶子节点是没有子节点的节点。对于这个问题，你可以通过递归的方式来解决：

1. 如果当前节点为空，那么它是叶子节点，并返回1；
2. 如果当前节点不是空，那么你需要递归地计算左子树和右子树的叶子节点数，然后将两者相加；
3. 最终结果就是根节点下的叶子节点总数。

Python伪代码示例如下：

def count_leaves(node):
    if node is None:  # 空节点视为叶子节点
        return 1
    elif node.left is None and node.right is None:  # 没有子节点的节点是叶子节点
        return 1
    else:
        return count_leaves(node.left) + count_leaves(node.right)

如果你需要具体的解题步骤或者有更复杂的输入情况，可以提供实际的二叉树结构或者数据，我会给出详细的解答过程。