想知道这两个几乎相同的答案的区别

Question

我正在做一个leetcode问题，你可以在这里检查:https://leetcode.com/problems/binary-tree-preorder-traversal以下是我第一次回答的错误答案:

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

这是我第二次通过测试的答案:

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

如果你有一个leetcode帐户你可以点击上面的链接,复制我的两个答案的代码和运行每个区域,你可以发现输入"(1、2、3)",这表示只有左分支的树在每个树节点,只能通过第二个代码在第一个,最左侧节点的值(在本例中,3)不包括在向量的问题问。我想知道我的第一个答案出了什么问题，导致了结果的不同。

我知道第一个代码看起来很奇怪和乏味，我只是想知道为什么它不能正常工作。

我会非常感谢你们这些帮助我的人。

Answer 1

预序遍历需要访问树中的所有节点。

第一个版本你有这些行:

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

如果root->left不为空，则执行return语句，并在返回对preorderTraversal的递归调用后导致函数的执行结束。

这意味着如果root->left不为空，整个右子树将不是访问。

第二个if也是错误的一致性原因(没有理由返回右子树，如果你不应该返回左子树)。

你的第二版向左和向右(按该顺序)执行递归，以确保根据preorder条件访问所有节点。