统计二叉树中度为 1 的结点 —— 布尔异或巧判

原始题目

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
int count = 0;
void countDegree1(TreeNode* root) {
    if (root == nullptr) return;
    if ((root->left != nullptr) != (root->right != nullptr)) count++;
    countDegree1(root->left);
    countDegree1(root->right);
}
countDegree1(root);
cout << count;

问：程序运行后输出什么？

答案

输出 0

解析

这段代码的功能是统计二叉树中度为 1（恰好只有 1 个子节点）的结点个数，采用的是对两个布尔值做异或（XOR）的技巧。

关键判断

if ((root->left != nullptr) != (root->right != nullptr)) count++;

• root->left != nullptr 是布尔值：true 表示有左孩子。
• root->right != nullptr 是布尔值：true 表示有右孩子。
• 两个布尔值做 !=，结果仅当“一个有孩子、另一个没有”时才为 true，即结点的度恰好为 1。

还原树结构

        1
       / \
      2   3
     / \
    4   5

易错点总结

• 度 = 子节点个数：叶子结点度为 0，满结点的度为 2，只有“独苗”结点（仅左或仅右）度为 1。
• XOR 写法 (a) != (b) 比写 if (a && !b || !a && b) 更简洁，是判断“恰好满足一个”的常用技巧。
• 递归顺序：先本结点、再左、再右，等价于前序遍历，遍历完整棵树。

思考题

如果把判断改成 if (root->left != nullptr && root->right != nullptr) count++;，count 会变成多少？