如何使用递归获得二叉树中的所有非叶节点？

要使用递归获得二叉树中的所有非叶节点，首先需要理解二叉树的基本结构和递归的工作原理。

基础概念

二叉树：每个节点最多有两个子节点的树结构，通常称为“左”和“右”子节点。
叶节点：没有子节点的节点。
非叶节点：至少有一个子节点的节点。

递归方法

递归是一种算法设计技巧，它允许一个函数调用自身来解决问题的一部分，直到达到基本情况。

示例代码

以下是一个使用Python编写的示例代码，展示如何递归地获取二叉树中的所有非叶节点：

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

def get_non_leaf_nodes(node):
    if node is None:
        return []
    
    # 如果当前节点是非叶节点，则添加到结果中
    non_leaf_nodes = []
    if node.left or node.right:
        non_leaf_nodes.append(node)
    
    # 递归地检查左右子树
    non_leaf_nodes.extend(get_non_leaf_nodes(node.left))
    non_leaf_nodes.extend(get_non_leaf_nodes(node.right))
    
    return non_leaf_nodes

# 构建一个简单的二叉树
#       1
#      / \
#     2   3
#    / \ / \
#   4  5 6  7
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3, TreeNode(6), TreeNode(7))

# 获取所有非叶节点
non_leaf_nodes = get_non_leaf_nodes(root)
for node in non_leaf_nodes:
    print(node.value)  # 应该输出 1, 2, 3

解释

TreeNode类：定义了二叉树节点的结构。
get_non_leaf_nodes函数：这是一个递归函数，它检查每个节点是否为非叶节点（即是否有子节点）。如果是，则将其添加到结果列表中，并继续递归地检查其左右子节点。
构建二叉树：创建了一个简单的二叉树用于测试。
调用函数并打印结果：调用get_non_leaf_nodes函数并打印出所有非叶节点的值。