二叉树前序遍历

前序遍历：顶-左-右

C++迭代

一个通用模板，比下面自己写的效率差点：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*>node;
        if(!root) return ans;
        node.push(root);
        while(!node.empty()){
            TreeNode* cur = node.top();
            node.pop();
            if(cur != nullptr){
                if(cur->right) node.push(cur->right);
                if(cur->left ) node.push(cur->left );
                node.push(cur);
                node.push(nullptr);
                ###右-左-上-nullptr###
            }
            else{
                ans.push_back(node.top()->val);
                node.pop();
            }
        }
        return ans;
    }
};

自己写的：
1.先入栈后访问
2.右左子树入栈

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        vector<TreeNode*> node;
        if(root == NULL) return ans;
        node.push_back(root);
        while(!node.empty()){
            TreeNode* cur = node.back();
            node.pop_back();
            ans.push_back(cur->val);
            #先push右边再左边，这样取的时候就是先取左边再右边
            if(cur->right != NULL) node.push_back(cur->right);
            if(cur->left != NULL) node.push_back(cur->left);
        }        
        return ans;
    }
};

C++递归

class Solution {
public:
    vector<int> ans;

    vector<int> preorderTraversal(TreeNode* root) {
        if(root == NULL) return ans;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root){
        ans.push_back(root->val);
        if(root->left != NULL) dfs(root->left);
        if(root->right != NULL) dfs(root->right);
    }
};

上面这种写复杂了，下面是简化后的：

class Solution {
public:
    vector<int> ans;

    vector<int> preorderTraversal(TreeNode* root) {
        if(root){
            ans.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return ans;
    }
};