这段代码在geeks for geeks for left view of tree中没有返回期望的输出

Question

这段代码没有在极客的极客中返回所需的输出。对于树的左视图

vector<int> leftView(Node *root)
{
vector<int> ans;

if (root==NULL)
return ans;

else if(root->left==NULL&&root->right!=NULL){
ans.push_back(root->data);
leftView(root->right);
}

else{
ans.push_back(root->data);
leftView(root->left);
}
return ans;
}

Answer 1

让我们看看你的代码。

vector<int> leftView(Node *root)
{
vector<int> ans;

if (root==NULL)
return ans;

else if(root->left==NULL&&root->right!=NULL){
ans.push_back(root->data);
leftView(root->right);
}

else{
ans.push_back(root->data);
leftView(root->left);
}
return ans;
}

我们甚至不清楚这段代码应该做什么，但让我们看看它是做什么的。

如果传入一个nullptr，它将返回一个空数组。那很酷。

如果传入一个没有左分支但有右分支的节点:

1. 将数据放入ans。
2. 在右边递归，但是丢掉结果。
3. 返回ans。

否则，你有一个左节点，你做几乎相同的事情，但你仍然扔掉结果。

所以最后，您将返回的唯一东西是来自根节点的数据。

那可能不是你真正想要的。你可能想积累结果。我会把向量作为第二个参数传递给方法然后继续传递下去。您最终将从根节点获得数据，沿着树一直到树的底部(某种程度上)。至少它会有更多的数据。如果这是你想要的。

Answer 2

当root不为NULL，但root->left和root->right都为NULL时，您不输出任何内容。但是push_back应该在left和right之前被遍历。更重要的是，它们都应该被遍历，而不是以非此即彼的方式。

同样，当递归调用leftView()时，您将忽略它返回的任何数据。这就是你的输出不是你期望的主要原因。

试试这样做(基于这个解决方案):

void leftViewHelper(Node *root, int level, int& max_level, std::vector<int> &ans)
{
if (root == NULL)
return;

if (max_level < level) {
ans.push_back(root->data);
max_level = level;
}

leftViewHelper(root->left, level + 1, max_level, ans);
leftViewHelper(root->right, level + 1, max_level, ans);
}

vector<int> leftView(Node *root)
{
vector<int> ans;
int max_level = 0;
leftViewHelper(root, 1, max_level, ans);
return ans;
}