二叉树中序遍历递归代码无法正确存储节点值问题求助

问题描述 #

编写了一段递归代码意图遍历二叉树（自称中序遍历，但代码实现是前序逻辑），但无法正确存储所有非空节点的值。添加打印语句后发现，每个递归调用里的节点值都存入了vector，但针对测试用例[1, NULL, 3,2]（结构：根节点1无左子节点，右子节点3的左子节点是2），最终返回的vector未包含所有节点值。

原代码 #

vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> nodesVal;
    int i = 0;  // initialize the position to check the element in the vector during recursion
    if(root!=0) {
        
        printf("value of root->val is %d\n", root->val);
        
        nodesVal.push_back(root->val);  // Did I not store the non-NULL node's value in this line here?  for every recursive call whether it is right, left child during the recursion?  so what is missing?
        
        printf("vector's value at position i:  %d\n", nodesVal[i]); 
        

        if(root->left) {
            i++;
            preorderTraversal(root->left);
        }
        if (root->right) {
            i++;
            preorderTraversal(root->right);
        }   
    }
    return nodesVal;
}

打印输出 #

value of root->val is 1
integer value 1           // this here output the vector's value at position 0 which indeed is value 1. So it seems correct. 

value of root->val is 2
integer value 2        // this here output the vector's value at position 1 which indeed is value 2. So it seems correct. 


value of root->val is 3
integer value 3            // this here output the vector's value at position 2 which indeed is shown to be 3

问题原因 #

1. 每个递归调用都生成独立的vector实例
   每次调用preorderTraversal函数时，都会新建一个nodesVal向量。递归访问子节点时，子调用的向量和父调用的向量完全无关，父调用不会将子调用的向量内容合并到自己的向量中。比如：

   • 调用preorderTraversal(1)时，创建的向量只存入了1；
   • 随后调用preorderTraversal(3)，这个子调用的向量存入了3，再调用preorderTraversal(2)存入2，但这些子向量的内容不会被父向量获取；
   • 最终返回的只有最上层调用的向量，也就是仅包含[1]。

2. 变量i无意义且存在逻辑误导
   每个递归调用里的i都是独立初始化的，子调用的i和父调用的i没有关联。你看到的打印结果，其实是每个子调用自己向量的第0个元素，而非父向量的第i个位置——比如访问节点2时，打印的是自己向量里的第0个元素2，不是父向量的第1个位置，这完全是误解。另外，push_back会自动把元素追加到向量末尾，根本不需要手动维护i这个变量。

修正方案 #

方案一：通过引用传递共享向量（推荐，效率更高） #

让所有递归调用操作同一个向量，用引用参数传递：

// 辅助递归函数，用引用传递向量
void traverse(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    // 前序遍历顺序：根 -> 左 -> 右
    result.push_back(root->val);
    traverse(root->left, result);
    traverse(root->right, result);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    traverse(root, result);
    return result;
}

如果要实现中序遍历，只需调整push_back的位置：

void traverse(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    // 中序遍历顺序：左 -> 根 -> 右
    traverse(root->left, result);
    result.push_back(root->val);
    traverse(root->right, result);
}

方案二：合并递归返回的向量 #

每次递归调用后，将子树的遍历结果合并到当前向量中：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    // 添加当前节点值
    result.push_back(root->val);
    // 合并左子树遍历结果
    vector<int> leftRes = preorderTraversal(root->left);
    result.insert(result.end(), leftRes.begin(), leftRes.end());
    // 合并右子树遍历结果
    vector<int> rightRes = preorderTraversal(root->right);
    result.insert(result.end(), rightRes.begin(), rightRes.end());
    
    return result;
}

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