顺序树遍历在遍历时保存节点的值

Question

我有一段代码来遍历一个"有序"的树时尚。

然而，我只是不确定是什么错了，因为当节点不是NULL时，它似乎没有存储相应节点的值。

我添加了各种打印语句来检查节点的值是否应该在递归运行时存储。从print语句来看，只要节点非null，那么它们的值应该已经被存储了。但不知何故，它不是这样的情况下，当我运行以下存储树的值在向量nodesVal:

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 %dn", 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:  %dn", nodesVal[i]); 

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

这是cout打印的语句:

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

因此，当我检查第0，第1和第2个位置时，向量似乎能够存储值，但不知何故，如果不是[1,NULL, 3,2]的测试用例显示这是失败的:

下面是根在1的树，那么1没有左子结点，但是有一个右子结点1的子元素是3。标签为3的子节点也有左子节点，但没有右子节点。

1
null       3 
2

Answer 1

问题是递归调用返回的向量被忽略了。所有递归发生的集合现在都丢失了，您的本地向量仍然只有一个条目。

当您查看局部向量变量的声明和函数末尾的return时，您可以看到唯一发生在它身上的事情是单个push_back调用。

有不同的方法可以让它工作:

1. 只有一个向量，并将其作为引用参数传递。

   void preorderTraversal(TreeNode* root, vector<int> &nodesVal) {
   if (root != nullptr) {            
   nodesVal.push_back(root->val);
   if (root->left) preorderTraversal(root->left, nodesVal);
   if (root->right) preorderTraversal(root->right, nodesVal);
   }
   }
   

   …然后调用者不应该期望向量作为返回值，而应该提供一个空向量作为参数。调用后，该vector对象将被填充。

2. 使用从递归调用中获得的向量作为返回值，并将其连接到本地向量

   vector<int> preorderTraversal(TreeNode* root) {
   vector<int> nodesVal;
   if (root != nullptr) {            
   nodesVal.push_back(root->val);
   if (root->left) {
   vector<int> leftVals = preorderTraversal(root->left);
   nodesVal.insert(nodesVal.end(), leftVals.begin(), leftVals.end());
   }
   if (root->right) {
   vector<int> rightVals = preorderTraversal(root->right);
   nodesVal.insert(nodesVal.end(), rightVals.begin(), rightVals.end());
   }
   }
   return nodesVal;
   }