1.二叉链表的递归算法:1)遍历算法(先 序,中序以及后序递归遍历算法)2)统计度 为1结点的个数

1) 二叉链表的递归遍历算法分为先序遍历、中序遍历和后序遍历。

- 先序遍历：先访问根节点，然后递归遍历左子树和右子树。

def preorder_traversal(root):
    if root is None:
        return
    print(root.val)
    preorder_traversal(root.left)
    preorder_traversal(root.right)

- 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left)
    print(root.val)
    inorder_traversal(root.right)

- 后序遍历：先递归遍历左子树和右子树，最后访问根节点。

def postorder_traversal(root):
    if root is None:
        return
    postorder_traversal(root.left)
    postorder_traversal(root.right)
    print(root.val)

2) 统计度为1结点的个数：

在二叉树中，度为1的结点只有一棵子树，所以我们可以递归遍历二叉树，对于每个结点，判断其左右子树是否为空。如果左右子树中只有一个非空，则该结点的度为1。

def count_degree_one_nodes(root):
    if root is None:
        return 0
    count = 0
    if root.left is not None and root.right is None:
        count += 1
    elif root.left is None and root.right is not None:
        count += 1
    count += count_degree_one_nodes(root.left)
    count += count_degree_one_nodes(root.right)
    return count