树的存储和遍历（必做题）（1）编码实现树的两种存储结构：双亲表示法和孩子表示法；（2）基于树的孩子表示法实现树的前序遍历、后序遍历和层序遍历；（3）求解树的深度。编写出满足以上题目要求的C＋+代码要求

（1）在C++中，我们可以使用结构体来表示树的节点，并分别实现双亲表示法（也称为链式存储）和孩子表示法。

**双亲表示法（链式存储）**

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

**孩子表示法（数组存储）**

struct TreeNode {
    int val;
    vector<TreeNode*> children; // 存储指向孩子的指针
    TreeNode(int x) : val(x) {}
};

（2）以下是基于孩子表示法实现的三种基本遍历算法：

**前序遍历（根-左-右）**

void preOrder(TreeNode* root) {
    if (root != nullptr) {
        cout << root->val << " ";
        for (auto& child : root->children) {
            preOrder(child);
        }
    }
}

**后序遍历（左-根）**

void postOrder(TreeNode* root) {
    if (root != nullptr) {
        for (auto& child : root->children) {
            postOrder(child);
        }
        cout << root->val << " ";
    }
}

**层序遍历（水平优先）**

void levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        for (auto& child : node->children) {
            q.push(child);
        }
    }
}

（3）求解树的深度（即最远叶子节点到根的距离）

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}