wanna know the difference of these two almost same answers-CodePudding

I'm doing a leetcode problem which you can check it here:https://leetcode.com/problems/binary-tree-preorder-traversal here's my first time answer which is a wrong answer:

class Solution {
public:
    TreeNode* preorderTraversal(TreeNode* root, vector<int> &res){
        if(root) res.push_back(root->val); else return nullptr;
        if(root->left) return preorderTraversal(root->left,res);
        if(root->right) return preorderTraversal(root->right,res);
        return root;
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderTraversal(root,res);
        return res;
    }
};

And here's my second time answer which passed the test:

class Solution {
public:
    void preorderTraversal(TreeNode* root, vector<int> &res){
        if(root) res.push_back(root->val); else return;
        preorderTraversal(root->left,res);
        preorderTraversal(root->right,res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderTraversal(root,res);
        return res;
    }
};

if you had a leetcode account you can simply click the link above and copy my two answers in the code area and run each of both, you can then find out that inputs like "[1,2,3]", which represent trees that only have left branches in every tree node, can only pass the second code while in the first one, the left most node's value(in this example, 3) is not included in the vector that the problem ask for. I wonder what's wrong with my first answer that caused the difference in result.

I know the first code seem weird and tedious, I just wonder why it can't work correcetly.

I'll be really thankful to you guys who help me out.

CodePudding user response：

Preorder traversal requires to visit all the nodes in the tree.

In your 1st version you have these lines:

if(root->left) return preorderTraversal(root->left,res);
if(root->right) return preorderTraversal(root->right,res);

If root->left is not null the return statement will be executed, and will cause the function's execution to end after the recursive call to preorderTraversal will return.

This means that if root->left is not null the whole right sub tree will not be visited.

The second if is also wrong for consistency reasons (no reason the return the right subtree if you should never return the left one).

Your 2nd version performs recursion both to the left and to the right (in that order) which ensures all the nodes are visited according to the preorder criterion.