# What's wrong with my recursive code?

• There is an extra 1 in the result on OJ.
I test locally, it is correct.
Thank you for pointing out my fault first.

``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
static vector<int> v = {};
if (root == NULL) {
return v;
}
inorderTraversal(root->left);
v.push_back(root->val);
inorderTraversal(root->right);
return v;
}
};``````

• Well, the problem is, the vector would be initialized every time when you call the function recursively, so, you should add the whole vector into "v" when doing inorderTraversal(root->left), and inorderTraversal(root->right);. In java, if we define an ArrayList<Integer> list beforehand, when you call the function recursively, we need to use : list.addAll(inorderTraversal(root.left)); list.add(root.val); list.addAll(inorderTraversal(root.right));

• No it is static vector, it won't initialize every time.

• sorry, not good at c++

• I also tested locally on my machine and it worked. From my understanding, this approach should work, and should be platform independent, so I would be very curious to see an explanation of why it is rejected.

• If I had to venture a guess, it would be that your function is executed consecutively by the test program and your result vector is never cleared as it's static. I imagine the first test input is {} which does nothing, followed by {1}, which adds 1, and then {1,2} which leads incorrectly to (1,2,1) as you said.

• You got the point! Just set the result vector as global and the error solved.

• A little change can do~

``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode *root) {
if(root ==  NULL) return res;
inorderTraversal(root->left);
res.push_back(root->val);
inorderTraversal(root->right);
return res;
}
};``````

• Hey there!

First, I'd like to show you my accepted python solution.

``````class Solution:
# @param root, a tree node
# @return a list of integers
def inorderTraversal(self, root):
# @Recursive Code.
result = []
if root is None:
return result
result.extend(self.inorderTraversal(root.left))
result.append(root.val)
result.extend(self.inorderTraversal(root.right))
return result
``````

It is quite simple because there is a 'extend' method in python. So we can merge two lists.Don't forget inorderTraversal returns a list(or a vector in C++, anyway). But in your solution, you don't do any work to handle the list returned. Therefore, you cannot get the right answer.

I have also tried your solution. But in C++, there is no direct way to implement the extend method like in python. So you'd try to use insert instead.

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v = {};
vector<int> vLeft = {};
vector<int> vRight = {};
if (root == NULL) {
return v;
}
vLeft = inorderTraversal(root->left);
v.insert(v.end(), vLeft.begin(), vLeft.end());
v.push_back(root->val);
vRight = inorderTraversal(root->right);
v.insert(v.end(), vRight.begin(), vRight.end());
return v;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.