若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。 A. 后序 B. 前序 C. 中序 D. 按层次

答案是B. 前序遍历最合适。

交换所有分支结点的左右子树，可以采用递归的方法，具体实现是：对于当前节点，先交换其左右子树，然后递归地对左右子树分别进行同样的操作。显然，前序遍历是最合适的遍历方法，因为在遍历到一个节点时，可以直接进行左右子树的交换操作，然后分别递归遍历左右子树。其他遍历方法则无法直接进行交换操作，需要额外的处理。

相关问题

设二叉树采用二叉链表存储，设计递归算法实现二叉树中所有结点的左右孩子交换。

算法思路：

1. 如果二叉树为空，直接返回；
2. 如果二叉树不为空，交换当前节点的左右孩子；
3. 递归交换当前节点的左子树和右子树。

代码实现：

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

def swapChildren(root):
    if not root:
        return
    root.left, root.right = root.right, root.left
    swapChildren(root.left)
    swapChildren(root.right)

测试样例：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

swapChildren(root)

# 遍历交换后的二叉树
def preorder(root):
    if not root:
        return
    print(root.val, end=' ')
    preorder(root.left)
    preorder(root.right)

preorder(root) # 1 3 2 7 6 5 4

已知二叉树采用二叉链表存储结构，编写算法统计二叉树中的叶子结点树

在二叉链表存储结构中，二叉树的每个节点由一个数据域和两个分别指向左右子树的指针域组成。叶子节点是指没有子节点的节点。统计二叉树中叶子节点的数量可以通过递归遍历的方式实现。下面是一个统计叶子节点数量的算法示例：

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

def countLeaves(node):
    # 如果当前节点为空，返回叶子节点数为0
    if node is None:
        return 0
    # 如果当前节点是叶子节点，返回叶子节点数为1
    if node.left is None and node.right is None:
        return 1
    # 否则，递归计算左右子树的叶子节点数量，并返回它们的和
    return countLeaves(node.left) + countLeaves(node.right)

# 示例使用：
# 创建一个二叉树的节点
#        1
#       / \
#      2   3
#     /   / \
#    4   5   6
#   /
#  7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.left.left.left = TreeNode(7)

# 统计叶子节点数量
leaf_count = countLeaves(root)
print("叶子节点的数量是:", leaf_count)

在这个示例中，`countLeaves` 函数递归地遍历二叉树的每个节点，并统计叶子节点的数量。如果当前节点为空，则返回0，表示没有找到叶子节点；如果当前节点没有子节点，则返回1，表示找到了一个叶子节点；如果当前节点有子节点，则递归地对其左右子树调用 `countLeaves` 函数，并将结果相加，最后返回叶子节点的总数。