统计二叉树结点个数pta

统计二叉树的节点个数通常涉及到对二叉树的遍历，特别是前序遍历、中序遍历或后序遍历。以下是几种常见的方法：

1. **递归法**：对于一棵二叉树，如果根节点存在，则它的节点个数等于左子树节点数加上右子树节点数加一（因为根节点本身也算一个）。这个过程可以用递归来实现。

2. **迭代法（栈）**：可以使用栈数据结构来进行非递归的前序遍历。从根节点开始，每访问一个节点就将其左右子节点依次入栈。当遍历到叶子节点时，说明已经统计完了所有节点，此时栈内元素个数就是节点总数减一。

3. **迭代法（Morris 遍历）**：这是一种空间效率较高的方法，利用线索二叉树的概念，通过修改原树结构达到“无额外存储空间”的效果，遍历过程中直接计算节点总数。

**Python 示例** (仅做概念演示，未包含边界条件检查)：

def count_nodes(root):
    if root is None:
        return 0

    # Morris遍历示例，这里假设root.left 和 root.right 指向空节点
    current = root
    count = 0
    while current:
        if not current.left:
            count += 1
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                count += 1
                current = current.right

    return count