如何修正计算二叉树中家庭最小所需手机数量的代码

给定一棵代表家庭成员的二叉树，需计算该家庭满足通信条件所需的最少手机数量。条件为：每个人可与父母、子女共享手机，但共享的手机无法被再次共享。以下是我编写的代码，请问如何修改以得到符合要求的输出？

int minPhones(struct TreeNode* root){

    //base case

    if(root == NULL)
    {
        return 0;
    }

    int phones = 0;
    int shared = 2;
    int phonesNeeded(struct TreeNode* node)
    {
        if(node == NULL)
        {return 0;}
        if((node->left == NULL ||  (node->left->left == NULL && node->left->right == NULL))&& (node->right == NULL ||  (node->right->left == NULL && node->right->right == NULL)))
        {
            shared = 1;
            return 1;
        }
        if(shared == 1)
        {
            shared = 0;
            return 0;
        }
        else if(shared == 0)
        {
            return 1;
        }
        return phonesNeeded(node->left) + phonesNeeded(node->right);
    }
    phones = phonesNeeded(root) + 1;
    return phones;
}

原代码的核心问题在于使用全局变量shared传递状态，递归过程中不同节点的状态会互相干扰，且逻辑仅覆盖了局部场景，未完整处理所有节点的状态传递。

正确的做法是通过递归函数返回节点的状态，以此决定当前节点是否需要手机，以及能否为父节点提供共享：
我们定义每个节点的三种状态：

• 0：节点无手机，且无法从子节点共享，需要自己配备手机
• 1：节点有手机（自己的或共享父母的），可以提供给子节点共享
• 2：节点无手机，但已共享子节点的手机，无法再为父节点提供共享

基于此，编写递归函数，同时统计所需手机总数：

#include <stdio.h>
#include <stdlib.h>

// 假设TreeNode结构定义如下
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 递归函数：返回节点状态，同时通过指针参数统计手机数量
int dfs(struct TreeNode* node, int* count) {
    if (node == NULL) {
        // 空节点，视为可以提供共享（不影响逻辑）
        return 1;
    }

    int left = dfs(node->left, count);
    int right = dfs(node->right, count);

    // 如果左右子节点都无法提供共享（状态0），当前节点必须自己买手机
    if (left == 0 && right == 0) {
        (*count)++;
        return 1; // 当前节点有手机，可以提供给父节点共享
    }

    // 如果左右子节点至少有一个能提供共享（状态1），当前节点可以共享子节点的手机
    if (left == 1 || right == 1) {
        return 2; // 当前节点无手机，已共享子节点的，无法给父节点提供共享
    }

    // 如果左右子节点都是状态2（共享了它们的子节点），当前节点需要自己买手机
    if (left == 2 && right == 2) {
        (*count)++;
        return 1;
    }

    // 其他情况默认返回状态1（实际不会走到这里）
    return 1;
}

int minPhones(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    int count = 0;
    int rootState = dfs(root, &count);

    // 如果根节点状态是0（无手机且无法共享），需要额外加1
    if (rootState == 0) {
        count++;
    }

    return count;
}

• 递归过程中通过count指针累计手机数量，避免全局变量的干扰
• 每个节点根据左右子节点的状态，决定自身是否需要购买手机，以及自身的状态
• 根节点没有父节点，所以如果根节点状态为0（无法共享子节点），必须额外配备一部手机

内容的提问来源于stack exchange，提问作者Phani P