递归算法求解二叉树中度为2的节点数

递归算法可以有效地解决二叉树中度为2的节点（也称为度为2的分支或结点）的问题。在这个问题上，我们通常会考虑以下步骤：

1. **基本情况**：如果给定的二叉树为空，那么它自然没有度为2的节点，返回0。

2. **递归情况**：对于非空的二叉树，我们需要分别检查左子树和右子树：
- 计算左子树中度为2的节点数。
- 计算右子树中度为2的节点数。
- **关键操作**：增加当前节点自身度为2的情况，即当前节点有两个子节点。这发生在当且仅当`left_child`（左孩子）存在并且`right_child`（右孩子）也存在时。
- 将左右子树的结果相加，加上当前节点的特殊情况。

递归公式可以表示为：

def count_degree_two(root):
    if root is None:
        return 0
    left_count = count_degree_two(root.left)
    right_count = count_degree_two(root.right)
    
    # 如果当前节点有两个子节点，则计数加1
    degree_two_nodes = (left_count + right_count) + int(root.left and root.right)

    return degree_two_nodes

其中，`root`是对二叉树根节点的引用。

相关问题

递归算法 求二叉树的高度

要求二叉树的高度，可以使用递归算法来实现。下面是一个示例的递归算法，用于计算二叉树的高度：

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

def get_tree_height(root):
    if root is None:  # 如果根节点为空，说明是空树，高度为0
        return 0
    else:
        left_height = get_tree_height(root.left)  # 递归计算左子树的高度
        right_height = get_tree_height(root.right)  # 递归计算右子树的高度
        return max(left_height, right_height) + 1  # 返回左右子树中较大的高度加1

在这个递归函数中，我们首先判断根节点是否为空，如果为空，则返回0，因为空树高度为0。否则，我们递归计算左子树和右子树的高度，然后取左右子树中较大的高度，并加1，即为整个二叉树的高度。

使用这个递归函数，可以方便地求解任意二叉树的高度。

设二叉树采用二叉链表存放，设计非递归算法求二叉树的高度

非常好的问题！对于这个问题，我可以给你一个基于迭代的算法来求解。该算法使用一个栈来模拟递归过程，具体步骤如下：

1. 如果二叉树为空，直接返回0.
2. 初始化一个栈，将树的根节点入栈，高度初始化为1.
3. 循环执行以下步骤：
1. 如果栈为空，说明已经遍历完了整棵树，返回高度.
2. 取出栈顶元素，如果该节点没有孩子，则继续循环.
3. 否则，将左右孩子分别入栈，并将高度+1.
4. 完成算法.

这个算法和递归算法非常类似，但是由于使用了一个栈来模拟递归，所以是一个非递归算法。希望这个算法对你有所帮助！