给定指定长度与字符二叉树，如何输出所有可生成的单词组合

问题原因分析 #

你的代码只能处理左斜树的核心问题有三个：

• 遍历节点时只递归访问了左子节点，完全没有处理右子节点的逻辑，右子树的所有节点都不会被纳入可选字符范围
• 递归参数传递逻辑错误，你现在递归传入root->left，导致下一层可选的字符只能是当前节点左子树内的节点，不符合「每个位置都可以选整棵树任意节点字符」的需求
• 额外的root2、root3参数设计冗余，完全可以简化逻辑

解决思路 #

你要实现的效果本质是：每个位置的字符都可以是二叉树中任意一个节点的字符，生成长度为n的所有可重复排列，可以用两种方案实现：

方案1：先收集所有节点字符再生成组合 #

• 第一步先遍历整棵二叉树，把所有节点的字符存入一个数组char_list
• 第二步用回溯法生成所有长度为n的可重复排列，每次从char_list里选一个字符加入当前字符串，长度达标就输出

方案2：直接在树遍历的过程中完成组合生成 #

不需要提前收集字符，每次选字符时都从根节点开始遍历整棵树，选中当前节点字符后进入下一层递归，再从头遍历整棵树选下一个字符

修正后的代码示例（方案2，逻辑更简洁） #

// 辅助函数：遍历整棵树，把每个节点的字符作为当前位的可选值
void dfs(Node* current_node, Node* root, string& word, int n) {
    if (current_node == nullptr) return;
    // 选中当前节点的字符
    word.push_back(current_node->data);
    if (word.size() == n) {
        cout << word << endl;
        word.pop_back();
        return;
    }
    // 下一位重新从根节点开始选所有可能的字符
    dfs(root, root, word, n);
    // 回溯，撤销选当前节点的操作，继续遍历其他分支的可选节点
    word.pop_back();
    // 遍历左子树的可选字符
    dfs(current_node->left, root, word, n);
    // 遍历右子树的可选字符
    dfs(current_node->right, root, word, n);
}

// 对外调用的入口函数
void printWords(Node* root, int n) {
    if (root == nullptr || n <= 0) return;
    string word;
    dfs(root, root, word, n);
}

上述代码针对你给出的a带左右子节点b、c的二叉树，n=2时可以输出你要求的全部9种组合。如果需要去重，可以用set容器存储结果最后统一输出即可。

内容的提问来源于stack exchange，提问作者KodaWantsASoda