c++ - 关于前序树遍历

Question

我为递归二叉树先序遍历编写了以下代码片段:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    std::vector<int> myVec;
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==NULL)
            return vector<int>();

        myVec.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);

        return myVec;
    }
};

虽然这段代码运行并产生了预期的输出，但我不确定这是否正确；因为当我调用preorderTraversal(root->left);和 preorderTraversal(root->right);我没有使用它们返回的值( vector<int> s)。所以，

1. 这是正确的吗？
2. 如果不是，那我该如何纠正这个代码？

Answer 1

是的，调用一次就对了。如果不是，则 myVec vector 不会被清除。

事实上，每次调用 preorderTraversal，除了最上面的那个和从它到左边的路径，都会返回一些没有多大意义的中间状态。如果我是你，我会重构这段代码以隐藏类中的中间值:

class Solution {
private:
    std::vector<int> myVec;

    void traverse(TreeNode* root) {
        if (root == NULL)
            return;

        myVec.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        myVec.clear();
        traverse(root);
        return myVec;
    }
};