What's wrong with my recursive code?


  • 3
    B

    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;
        }
    };

  • 0
    X

    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));


  • 0
    B

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


  • 0
    X

    sorry, not good at c++


  • 0
    T

    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.


  • 7
    J

    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.


  • 0
    R

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


  • 0
    R

    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;
     }
    };

  • 0
    V

    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;
        }
    };

Log in to reply
 

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