求解二叉树的宽度用c++递归实现

要计算二叉树的宽度，可以使用递归的方法。宽度定义为二叉树中任意一层节点的最大数量。我们可以通过遍历每个节点并记录每个深度上的节点数量来实现这一点。

以下是一个用C++递归实现计算二叉树宽度的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        std::vector<int> leftMost;
        int maxWidth = 0;
        dfs(root, 0, 0, leftMost, maxWidth);
        return maxWidth;
    }

private:
    void dfs(TreeNode* node, int depth, int index, std::vector<int>& leftMost, int& maxWidth) {
        if (!node) return;
        if (depth == leftMost.size()) {
            leftMost.push_back(index);
        }
        maxWidth = std::max(maxWidth, index - leftMost[depth] + 1);
        dfs(node->left, depth + 1, 2 * index, leftMost, maxWidth);
        dfs(node->right, depth + 1, 2 * index + 1, leftMost, maxWidth);
    }
};

int main() {
    // 构建一个示例二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);

    Solution solution;
    std::cout << "The width of the binary tree is: " << solution.widthOfBinaryTree(root) << std::endl;

    return 0;
}

在这个示例中，`TreeNode`结构体表示二叉树的节点，`Solution`类包含计算二叉树宽度的方法`widthOfBinaryTree`。我们使用一个辅助函数`dfs`来进行深度优先搜索，并记录每个深度上的节点数量。