        // 找到所有深度为 depth - 1 的节点，然后用 val 构造的新节点替换，替换时要注意顺序
        std::vector<TreeNode*> depth_1_nodes = [root, &depth]() {
            std::vector<TreeNode*> cur, next; // 层序遍历当前层，下一层
            cur.push_back(root);

            while (--depth) {
                for (auto t: cur) {
                    if (t->left) next.push_back(t->left);
                    if (t->right) next.push_back(t->right);
                }