力扣222题c语言

<think>好的，我现在需要解决用户的问题：用户想要找到LeetCode第222题的C语言解法。首先，我得确定第222题的具体内容是什么。LeetCode的题目编号对应的题目可能会变化，不过根据常见的题目列表，第222题应该是“完全二叉树的节点个数”（Count Complete Tree Nodes）。这个题目要求计算一个完全二叉树的节点个数，并且要求时间复杂度低于O(n)，也就是不能简单地遍历所有节点。 接下来，我需要回忆这个题目的解法。完全二叉树的特点是除了最后一层外，其他层都是满的，并且最后一层的节点都尽可能靠左。因此，可以利用这个特性来优化计算节点数的过程，避免遍历每一个节点。通常的解法是递归地判断左右子树的高度，如果左右高度相同，则左子树是满的，可以直接计算节点数，然后递归处理右子树；如果高度不同，则右子树是满的，而左子树需要递归处理。这种方法的时间复杂度是O(log n * log n)，因为每次递归都需要计算高度，而高度最多是log n层。 现在，我需要将这个思路转化为C语言的代码。首先，定义树节点的结构体，通常LeetCode的题目中树节点的定义是： struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; 然后，计算树的高度，这里需要注意的是，完全二叉树的高度可以通过一直向左走到底来计算。接着，递归地判断左右子树的高度，如果左高度大于右高度，说明右子树是满的，反之则左子树是满的。根据这个条件来计算节点数。 接下来，我需要考虑代码的正确性，比如处理空指针的情况，递归终止条件等。例如，当节点为空时，返回0；当左右子树高度相同时，左子树是满的，节点数为2^h -1加上根节点和右子树的节点数。 另外，要注意计算高度的方法，这里可能需要一个辅助函数来计算左子树的高度，因为完全二叉树的左子树高度可能会比右子树高1或者相等。 在编写代码时，还要注意位运算的使用，比如计算2^h可以用左移操作，即1 << h，但需要确保数据类型正确，避免溢出。 最后，测试代码是否正确，比如测试用例包括完全满二叉树、最后一层不满的情况等。 现在，我需要将这些步骤整合成C语言的代码，并确保语法正确，逻辑无误。同时，根据用户的要求，可能需要解释代码的思路，帮助用户理解解法。</think>### LeetCode 222题（完全二叉树的节点个数）C语言实现 #### 题目分析 给定一个**完全二叉树**的根节点，要求计算该树的节点个数。要求时间复杂度低于$O(n)$，即不能使用暴力遍历全部节点的方法[^1]。 #### 解题思路 1. **完全二叉树特性**：除最后一层外，其他层节点全部填满，最后一层节点尽可能靠左。 2. **高度计算**： - 左子树高度通过持续访问左子节点计算。 - 右子树高度通过持续访问左子节点计算（注意与左子树计算方式一致）。 3. **递归判断**： - 若左子树高度等于右子树高度，则左子树是满二叉树，直接计算左子树节点数，再递归处理右子树。 - 若高度不等，则右子树是满二叉树（但少一层），递归处理左子树。 #### C语言实现 ```c #include <math.h> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 计算左子树高度 int left_height(struct TreeNode* root) { if (!root) return 0; return 1 + left_height(root->left); } int countNodes(struct TreeNode* root) { if (!root) return 0; int left_h = left_height(root->left); int right_h = left_height(root->right); if (left_h == right_h) { // 左子树是满二叉树，节点数=2^h -1，加上根节点和右子树节点 return (1 << left_h) + countNodes(root->right); } else { // 右子树是满二叉树（高度比左子树少1） return (1 << right_h) + countNodes(root->left); } } ``` #### 代码说明 1. **时间复杂度**：$O(\log n \times \log n)$，每次递归需计算高度（$O(\log n)$），递归深度为树高（$O(\log n)$）。 2. **位运算优化**：`1 << h`等价于$2^h$，比`pow`函数更高效。 3. **递归终止条件**：当`root`为空时返回0。 ---