题目描述：根左右的遍历方式

方法1：递归

class Solution {
public:
    vector<int> vals;
    void pre_order(TreeNode* root){
        if(!root) return;
        vals.push_back(root->val);
        pre_order(root->left);
        pre_order(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        pre_order(root);
        return vals;
    }
};

方法2：非递归方式，先入栈右子树，再入栈左子树，因为栈是先进后出（注意空节点是不入栈的）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>vals;
        stack<TreeNode*>stk;
        if(!root) return vals;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* temp = stk.top();
            stk.pop();
            vals.push_back(temp->val);
            if(temp->right) stk.push(temp->right);
            if(temp->left) stk.push(temp->left);
        }
        return vals;
    }
};

和中序不一样，中序如下（与前序相似的写法）：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> temp;
        stack<TreeNode*> stk;
        if(!root) return temp;
        stk.push(root);

        TreeNode* a;

        while(!stk.empty()){
            if(root&&root->left){
                stk.push(root->left);
                root = root->left;
            }
            else{
                a = stk.top();
                temp.push_back(a->val);
                stk.pop();
                if(a->right){
                    stk.push(a->right);
                    root = a->right;
                }
            }
        }
        return temp;
    }
};