二叉树非叶子节点个数

题目描述

给定一棵用先序遍历（含空指针标记）表示的二叉树，使用 -1 表示空指针。请输出该二叉树的非叶子节点个数（至少有一个孩子的节点）。

先序序列构建二叉树模板代码:

struct Node {
    int data;
    Node* left, *right;
};

// 按先序创建，-1 表示空
Node* build() {
    int x; std::cin >> x;
    if (x == -1) return nullptr;
    Node* node = new Node();
    node->data = x;
    node->left  = build();
    node->right = build();
    return node;
}

int main() {
    Node* root = build();
}

输出格式

• 只有一行，一个整数，表示该二叉树的非叶子节点个数。

输入输出样例 #1

输入 #1

1 2 -1 -1 3 4 -1 -1 5 -1 -1

输出 #1

2

输入输出样例 #2

输入 #2

1 -1 -1

输出 #2

0

说明/提示

• 约定：输入使用先序遍历（根、左、右），以 -1 作为空指针占位。
• 非叶子节点指至少有一个孩子存在的节点（与“叶子节点”相对）。
• 建议先求总节点数与叶子数，再由关系式推导；或直接递归统计。