c++扩展二叉树前序遍历序列构建二叉树并计算该二叉树的深度

在扩展二叉树中，空节点用"#"表示。通过扩展二叉树的前序遍历序列可以构建该二叉树，具体步骤如下：

1. 从前序序列中取出第一个元素作为根节点；
2. 如果序列中下一个元素不是"#", 则递归创建其左子树；
3. 如果序列中下一个元素不是"#", 则递归创建其右子树。

以下是C++代码实现：

#include<iostream>
using namespace std;
 
struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x): val(x), left(nullptr), right(nullptr) {}
};
 
TreeNode* buildTree(string s, int& index){
    if(index >= s.size()){
        return nullptr;
    }
    if(s[index] == '#'){
        index++;
        return nullptr;
    }
    TreeNode* root = new TreeNode(s[index]);
    index++;
    root->left = buildTree(s, index);
    root->right = buildTree(s, index);
    return root;
}
 
int maxDepth(TreeNode* root){
    if(root == nullptr){
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}
 
int main(){
    string s = "ABC##DE#G##F###";
    int index = 0;
    TreeNode* root = buildTree(s, index);
    cout << "该二叉树的深度为：" << maxDepth(root) << endl;
    return 0;
}