[数据结构与算法]Leetcode 二叉树的前序遍历

迭代法：

记录状态的迭代法：

typedef pair<int, TreeNode*> P;
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> out;
        stack<P> stk;
        if(root) stk.push(P(0, root));
        while(stk.size() > 0) {
            P temp = stk.top();
            stk.pop();
            if(!temp.second) continue;
            if(!temp.first) {
                stk.push(P(0, temp.second->right));
                stk.push(P(0, temp.second->left));
                stk.push(P(1, temp.second));
            } else {
                out.push_back(temp.second->val);
            }
        }
        return out;
    }
};

另一种迭代，在压入栈的时候，存储输出值。（与中序遍历仅有输出行的位置不同）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> out;
        while(root || stk.size() > 0){
            while(root){
                stk.push(root);
                out.push_back(root->val);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            root = root->right;
        }
        return out;
    }
};

递归法：

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