python/TangDou/XiTi/1403.cpp

#include <bits/stdc++.h>

using namespace std;

#pragma region 二叉树模板

//二叉树结点结构
typedef struct TreeNode {
    bool data;                            //结点数据
    string num;
    struct TreeNode *left;                  //左孩子
    struct TreeNode *right;                 //右孩子
} *BinaryTree; //定义BinaryTree为指向 struct TreeNode(结构体TreeNode)的指针


//通过字符串数据，按层遍历反向构建完全二叉树
BinaryTree RebuildBinaryTree(string *arr, int n) {
    //构建一个指针组成的数组
    vector<BinaryTree> trees;
    //遍历每一个字符串数组中的字符串，构建指针，然后将指针添加到指针数组中去
    for (int i = 0; i < n; i++) {
        //实例化指针
        BinaryTree tree = new TreeNode();
        tree->num = arr[i];
        tree->data = false;//指针为->，对象为.
        tree->left = NULL;
        tree->right = NULL;
        trees.push_back(tree);
    }
    //从下往上遍历
    /*
                  0
              1      2
            3   4  5   6
     */
    for (int i = trees.size() - 1; i > 0; i--) {
        //奇数
        if (i % 2 != 0) {
            trees[(i - 1) / 2]->left = trees[i];  //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
        } else//偶数
        {
            trees[(i - 1) / 2]->right = trees[i]; //好巧妙的 (i-1)/2，这个除法是整数除法，还带取整的，牛！
        }
    }
    return trees[0];//返回根节点
}


//前序遍历
void PreOrderTraverse(BinaryTree T) {
    //利用递归前序输出二叉树
    if (T) {
        cout << T->data << " ";
        PreOrderTraverse(T->left);
        PreOrderTraverse(T->right);
    }
}

//中序遍历
void InOrderTraverse(BinaryTree T) {
    //利用递归中序输出二叉树
    if (T) {
        InOrderTraverse(T->left);
        cout << T->data << " ";
        InOrderTraverse(T->right);
    }
}

//后序遍历
void PostOrderTraverse(BinaryTree T) {
    //利用递归后序输出二叉树
    if (T) {
        PostOrderTraverse(T->left);
        PostOrderTraverse(T->right);
        cout << T->data << " ";
    }
}

void PreOrderTraverseWithLevel(BinaryTree T, int level, vector<vector<BinaryTree>> &vec) {
    if (T) {
        if (vec.size() < level + 1) {
            vector<BinaryTree> arr;
            vec.push_back(arr);
        }
        vec[level].push_back(T);
        PreOrderTraverseWithLevel(T->left, level + 1, vec);
        PreOrderTraverseWithLevel(T->right, level + 1, vec);
    }
}

//层次遍历
void LevelOrderTraverse(BinaryTree T) {
    if (T) {
        vector<vector<BinaryTree>> vec;
        PreOrderTraverseWithLevel(T, 0, vec);
        for (int i = 0; i < vec.size(); i++) {
            for (int j = 0; j < vec[i].size(); j++) {
                cout << vec[i][j]->data << " ";
            }
            cout << endl;
        }
    }
}

#pragma endregion 二叉树模板
BinaryTree tree;

string doAction(BinaryTree T) {
    if (T->left == NULL && T->right == NULL)
        return T->num;
    if (!T->data) {
        //左子树
        T->data = true;
        return doAction(T->left);
    } else {
        //右子树
        T->data = false;
        return doAction(T->right);
    }
}

//转换整数到字符串
string intToStr(int n) {
    char str[256] = {0};
    sprintf(str, "%d", n);
    return str;
}

int main() {
    int n, l;
    cin >> n >> l;
    int count = pow(2, n) - 1;
    string arr[10000];
    for (int i = 0; i < count; ++i) {
        arr[i] = intToStr(i + 1);
    }
    //构建完全二叉树（满二叉树）
    tree = RebuildBinaryTree(arr, count);

    //l次掉落
    string nodeNum;
    for (int i = 0; i < l; ++i) {
        nodeNum = doAction(tree);
    }
    //输出结果
    cout << nodeNum << endl;
    return 0;
}